对于给定的素数 p 和整数 α,A 计算整数对 (n, k) 的数量,使得 0 ≤ k ≤ n ≤ A 且 $${\binom {n}{k}}$$ 可被 pα 整除。
由于答案可能相当大,因此打印答案对 109 + 7 进行模后的余数。
让我们提醒您,$${\binom {n}{k}}$$ 是从 n 个对象的集合中选择 k 个对象的方式数。
输入
第一行包含两个整数,p 和 α(1 ≤ p,α ≤ 109,p 是质数)。
第二行包含整数 A (0 ≤ A < 101000) 的小数记录,不带前导零。
输出
在单行中打印问题的答案。
示例
输入 #1
2 2 7
输出 #1
3
输入 #2
3 1 9
输出 #2
17
输入 #3
3 3 9
输出 #3
0
输入#4
2 4 5000
输出#4
8576851
注意
在第一个样本中,可被 4 整除的三个二项式系数为 $${ \binom { 4 } { 1 } } = 4$$、$${ \binom { 4 } { 3 } } = 4$$ 和 $${ \binom { 6 } { 3 } } = 20$$。