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.

输入输出样例

输入样例 #1

2 2
7

输出样例 #1

3

输入样例 #2

3 1
9

输出样例 #2

17

输入样例 #3

3 3
9

输出样例 #3

0

输入样例 #4

2 4
5000

输出样例 #4

8576851

说明

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