Wstęp do programowania w C++

Napisz program, który określi na ile sposobów możemy wydać jakąś resztę n mając do dyspozycji nominały 1, k, k², k³, ...

Wejście

W pierwszym wierszu jedna liczba naturalna dodatnia k nie większa niż milion.

W drugim wierszu jedna liczba q określająca liczba zestawów danych (nie większa niż milion).

W kolejnych q wierszach jedna liczba n reprezentująca resztę do wydania ( 1 <= n <= 1000000).

Wyjście

Dla każdego zestawu danych jedna liczba określająca ilość możliwych sposobów, na jakie możemy wydać resztę n. Wynik przedstaw modulo 10⁹+7.

Przykład

Wejście:
2
4
1
2
10
1000000

Output:
1
2
14
46394541