FRAKTAL - konkurs programistyczny

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 <= 10⁵, 1 <= n <= 10, 1 <= k <= 10).

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

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