Runda 16 [Basic] - Wir

Zadanie tygodnia

runda 16; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 32MB

Wir

Ach jakże ciężko jest płynąć po wzburzonym morzu! Twój statek przecina fale i coraz bliżej już do celu podróży. Jednak nagle okazuje się, że w pobliżu znajduje się groźny wir morski! Czy uda się uniknąć katastrofy?

Przyrządy pomiarowe na pokładzie zmierzyły parametry wiru - składają się one z dwóch liczb oraz - odpowiednio siły początkowej oraz współczynnika przyrostu. W każdej kolejnej minucie siła wiru wzmaga się - wynosi ona sumę sił wiru ze wszystkich poprzednich minut, powiększoną o współczynnik przyrostu. W pierwszej minucie jego siła wynosi tyle, ile siła początkowa.

Zatem jeśli , , to w pierwszej minucie siła wiru to , w drugiej , w trzeciej , w czwartej i tak dalej...

Wiesz, że będziecie przebywać w zasięgu wiru przez minut - zastanawiasz się zatem, jaka będzie suma wartości siły wiru ze wszystkich minut od pierwszej do -tej. Ponieważ wiesz, że ta liczba może być ogromna, interesuje Cię dla celów statystycznych jedynie jej reszta z dzielenia przez .

Wejście:

Jedyna linia wejścia zawiera trzy liczby całkowite - , oraz - kolejno wartość siły początkowej wiru, wartość współczynnika przyrostu oraz liczbę minut, jaką statek spędzi w bliskości wiru. ()

Wyjście:

Wyjście powinno się składać z jednej liczby - reszty z dzielenia sumy wartości siły wiru przez 17389, gdzie sumę liczymy od do -tej minuty.

Przykład:

Wejście:

Wyjście:

38