CF582D.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 109 + 7.

Let us remind you that is the number of ways k objects can be chosen from the set of n objects.

给定一个素数 $ p $ 以及整数 $ \alpha $、$ A $，请计算满足 $ 0 \leq k \leq n \leq A $ 且组合数

能被 $ p^\alpha $ 整除的整数对 $ (n, k) $ 的个数。

由于答案可能非常大，请输出答案对 $ 10^9 + 7 $ 取模的结果。

提醒：

表示从 $ n $ 个不同物体中选出 $ k $ 个物体的方法数（即二项式系数）。

The first line contains two integers, p and α (1 ≤ p, α ≤ 109, p is prime).

The second line contains the decimal record of integer A (0 ≤ A < 101000) without leading zeroes.

第一行包含两个整数 $p$ 和 $\alpha$（$1 \leq p, \alpha \leq 10^9$，且 $p$ 为质数）。

第二行包含整数 $A$ 的十进制表示（$0 \leq A < 10^{1000}$），不含前导零。

In the single line print the answer to the problem.

在单行中输出问题的答案。

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

在第一个样例中，有三个能被 4 整除的二项式系数：、 和 。