← 返回题目列表

Codeforces · 582/D

D. 二项式系数的数量

中文机器翻译题面 查看原题

对于给定的素数 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$$。