D. Количество биномиальных коэффициентов
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для заданного простого целого числа p и целых α, A посчитайте количество пар целых чисел (n, k) таких, что 0 ≤ k ≤ n ≤ A и делится на pα.

Поскольку ответ может быть очень большим, выведите его остаток от деления на 109 + 7.

Напомним, что — это количество сочетаний размера k из n предметов.

Входные данные

В первой строке содержатся два целых числа p и α (1 ≤ p, α ≤ 109, p — простое).

Во второй строке содержится десятичная запись целого числа A (0 ≤ A < 101000) без ведущих нулей.

Выходные данные

В единственной строке выведите ответ на задачу.

Примеры
Входные данные
2 2
7
Выходные данные
3
Входные данные
3 1
9
Выходные данные
17
Входные данные
3 3
9
Выходные данные
0
Входные данные
2 4
5000
Выходные данные
8576851
Примечание

В первом примере три биномиальных коэффициента, делящихся на 4, это , и .