Liczby spadkowe

Elfy liczą w systemie o podstawie b i uznają tylko liczby n-cyfrowe. Dodatkowo, ich bardzo wyczulone poczucie piękna każe im uznawać, że za piękne można uznać tylko takie liczby, które w zapisie w systemie o podstawie b (czyli jedynym prawidłowym) cyfry są zapisane w porządku nierosnącym (tj. pierwsza cyfra - najbardziej znacząca - jest niemniejsza niż druga, druga niemniejsza niż trzecia itd.).

Policz liczbę liczb pięknych dla elfów, które są podzielne przez p. Wynik wypisz modulo 1 000 000 007.

Wejście, wyjście

W pierwszej i jedynej linii wejścia są trzy liczby całkowite oddzielone spacjami: 2 <= n <= 1000 (długość liczby w zapisie o podstawie b), 2 <= b <= 20 (podstawa systemu) oraz 2 <= p <= 600.

Wypisać należy jedną liczbę - liczbę liczb pięknych (dla elfów), modulo 1 000 000 007.

Przykład

Dla danych:

6 10 3

prawidłowym wynikiem jest:

1674