Codeforces Round #803 (Div. 2)
20:21:07 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
D. Number of Binominal Coefficients
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
For a given prime integer $p$ and integers $α, A$ calculate the number of pairs of integers $(n, k)$, such that $0 ≤ k ≤ n ≤ A$ and is divisible by $p^{α}$.
As the answer can be rather large, print the remainder of the answer moduly $10^{9} + 7$.
Let us remind you that is the number of ways $k$ objects can be chosen from the set of $n$ objects.
Оролт
The first line contains two integers, $p$ and $α$ ($1 ≤ p, α ≤ 10^{9}$, $p$ is prime).
The second line contains the decimal record of integer $A$ ($0 ≤ A < 10^{1000}$) without leading zeroes.
Гаралт
In the single line print the answer to the problem.
Орчуулсан: [орчуулагдаж байгаа]
Жишээ тэстүүд
Оролт
2 2 7
Гаралт
3
Оролт
3 1 9
Гаралт
17
Оролт
3 3 9
Гаралт
0
Оролт
2 4 5000
Гаралт
8576851
Тэмдэглэл
In the first sample three binominal coefficients divisible by 4 are ,
and
.