Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_06_09 - Coś poszło nie tak!

W Bajtockim Instytucie Badań (BIB) profesor Algobit opracowuje właśnie modyfikację genetyczną DNA, która rozwiąże problem z niekontrolowanym rozmnażaniem się króliczków. Profesor planuje wydłużyć czas, po którym zwierzątka będą osiągały dojrzałość. Do tej pory już po miesiącu były wstanie kopulować, a w następnym rodziła się kolejna para młodych. Jak mówi pewne prawo: „jak coś ma pójść źle, to pójdzie”, i tym razem tak się stało. Rzeczywiście udało się profesorowi wydłużyć ten czas, ale zamiast jednej pary zaczęły rodzić się dwie. Kolejne próby rokowały jeszcze gorzej, zamiast jednej pary, rodziło się k par.

Twoim zadaniem jest zbadanie powagi problemu i napisanie programu, który określi ile par króliczków będzie po s miesiącach, zakładając, że zwierzątka osiągają dojrzałość po n miesiącach i potem regularnie co miesiąc rodzą się kolejne pokolenia. W każdym urodzeniu dana para  króliczków ma k par młodych. Zakładamy, że króliczki nie umierają. Na początku jest jedna para, która właśnie się urodziła - jest to miesiąc o numerze 0.

Wejście

W pierwszym wierszu trzy liczby całkowite dodatnie q, n, k gdzie q to liczba zapytań, dwie pozostałe liczby opisane są w zadaniu (q <= 105, 1 <= n <= 10, 1 <= k <= 10).

Każde z zapytań składa się z jednej liczby s (0 <= s <=106).

Wyjście

Dla każdego zapytania liczba par królików po s miesiącach modulo 1010101011.

Przykład

Wejście:
5 2 2
0
1
2
3
4

Wyjście:
1
1
1
3
5

W Bajtockim Instytucie Badań (BIB) profesor Algobit opracowuje właśnie modyfikację genetyczną DNA, która rozwiąże problem z niekontrolowanym rozmnażaniem się króliczków. Profesor planuje wydłużyć czas, po którym zwierzątka będą osiągały dojrzałość. Do tej pory już po miesiącu były wstanie kopulować, a w następnym rodziła się kolejna para młodych. Jak mówi pewne prawo: „jak coś ma pójść, źle to pójdzie”, i tym razem tak się stało. Rzeczywiście udało się profesorowi wydłużyć ten czas, ale zamiast jednej pary zaczęły rodzić się dwie. Kolejne próby rokowały jeszcze gorzej, zamiast jednej pary, rodziło się k par.

Twoim zadaniem jest zbadanie powagi problemu i napisanie programu, który określi ile par króliczków będzie po s miesiącach, zakładając, że zwierzątka osiągają dojrzałość po n miesiącach i potem regularnie co miesiąc rodzą się kolejne pokolenia. W każdym urodzeniu dana para  króliczków ma k par młodych. Zakładamy, że króliczki nie umierają.


Dodane przez:Marcin Kasprowicz
Data dodania:2016-10-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.