2668 - Number of Binominal Coefficients

2668.Number of Binominal Coefficients

Time Limit: 1s Memory Limit: 256MB

For a given prime integer p and integers \alpha ,A calculate the number of pairs of integers (n,k), such that 0 \le k \le n \le A and $2668_1.png$ is divisible by p \alpha . As the answer can be rather large, print the remainder of the answer moduly 109+7.Let us remind you that $2668_1.png$ is the number of ways k objects can be chosen from the set of n objects.

Input Format(From the terminal/stdin)

Input The first line contains two integers, p and \alpha (1 \le p, \alpha \le 109, p is prime). The second line contains the decimal record of integer A (0 \le A \lt 101000) without leading zeroes.

Output Format(To the terminal/stdout)

Output In the single line print the answer to the problem.

Sample Input 1

Copy

2 2
7
 · \n
 \n

Sample Output 1

Copy

3
 \n

Sample Input 2

Copy

3 1
9
 · \n
 \n

Sample Output 2

Copy

17
  \n

Sample Input 3

Copy

3 3
9
 · \n
 \n

Sample Output 3

Copy

0
 \n

Sample Input 4

Copy

2 4
5000
 · \n
    \n

Sample Output 4

Copy

8576851
       \n

Hints

In the first sample three binominal coefficients divisible by 4 are $2668_2.png$ , $2668_3.png$ and $2668_4.png$ .

Submit

请先登录

Submit

题解(0)