Problem 3: matcha

Cerință

Rareș, proaspăt student în București și dornic să cunoască orașul, a început să caute constant pe rețelele de socializare cele mai bune locuri pentru a savura o băutură răcoroasă și pentru a uita complet că trebuie să își caute j*b. După multe ore, primește un semn de la o entitate superioară planului terestru, apărându-i în feed un videoclip de la o legendă numită Paul Barbu, ce îl îndeamnă să savureze o matcha pe Primăverii. Astfel, pornește, fără nicio grijă în lume, către acest loc destinat numai celor demni de el.

Ajuns acolo, îl întâlneste pe Regele Neangajaților, Paul Barbu, și îi cere să îi destănuie secretele vieții fără a fi constrâns de un program 9-5. Acesta din urmă îi spune că îi va arăta tainele acestei băuturi doar dacă reușește să păcălească pe cineva să calculeze eficient numărul de kilograme de matcha necesare dezvoltării acestei industrii în ziua $n$ de la lansare, dat de următoarea zicală:

„În primele două zile se începe încet, cu câte un kilogram. Totuși, din a treia zi necesarul crește liniar, fiind nevoie de un total ce însumează de $a$ ori numărul din ziua precedentă și de $b$ ori numărul de acum 2 zile”.

Aflând acestea, Rareș postează pe un forum această problemă ce îl macină, iar voi, pregătindu-vă pentru concursul HackTheArt, încercați să îi dați de cap, considerând că este o problemă care vă poate ajuta să câștigați premiul cel mare pentru a vă permite să vă alăturați experienței de matcha pe Primăverii.

Date de intrare

Pe prima linie se vor găsi 3 numere, respectiv $n$ , $a$ , $b$ , cu semnificațiile din enunț.

Date de ieșire

Pe ecran se va afișa un singur număr, reprezentând cantitatea de matcha necesară industriei în ziua $n$ de la lansare. Dat fiind că acest număr poate fi foarte mare, se cere afișarea lui modulo $10^9 + 7$ .

Restricții și precizări

$3 \leq n \leq 10^9$ ;
$1 \leq a, b \leq 10^6$ ;
Poate chiar ne vedem la matcha pe Primăverii.

Exemplul 1

stdin

5 1 1

stdout

Exemplul 2