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.

Input

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.

Output

In the single line print the answer to the problem.

Note

In the first sample three binominal coefficients divisible by 4 are , and .