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.
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.
Dla danych:
6 10 3
prawidłowym wynikiem jest:
1674
[Zgłoś rozwiązanie] [Moje zgłoszenia]