A9996. 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.

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