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 .

Сэтгэгдлүүдийг ачааллаж байна...