Для заданного простого целого числа p и целых α, A посчитайте количество пар целых чисел (n, k) таких, что 0 ≤ k ≤ n ≤ A и 
делится на pα.
Поскольку ответ может быть очень большим, выведите его остаток от деления на 109 + 7.
Напомним, что — это количество сочетаний размера k из n предметов.
Выходные данные
В единственной строке выведите ответ на задачу.
Примечание
В первом примере три биномиальных коэффициента, делящихся на 4, это 
, 
и 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
7
|
3
|
|
2
|
3 1
9
|
17
|
|
3
|
3 3
9
|
0
|
|
4
|
2 4
5000
|
8576851
|