# D. Number of Binominal Coefficients

### гаралт стандарт гаралт

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 .

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