Number of Binominal Coefficients

给定质数 $p$ 和整数 $\alpha,A$，求满足 $0 \le k \le n \le A$ 且 $p^{\alpha}|\binom nk$ 的数对 $(n,k)$ 的个数。 $p,\alpha \le 10^9$，$A < 10^{1000}$，答案对 $10^9+7$ 取模。

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&lt;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 .