CF582D Number of Binominal Coefficients

给定一个素数 $p$ 和整数 $α, A$，计算有多少对整数 $(n, k)$，满足 $0 \leq k \leq n \leq A$，且 $\binom{n}{k}$ 可以被 $p^{α}$ 整除。 由于答案可能非常大，请输出答案对 $10^9+7$ 取模后的结果。 需要提醒的是，$\binom{n}{k}$ 表示从 $n$ 个物体中选出 $k$ 个物体的方案数。

第一行包含两个整数 $p$ 和 $α$（$1 \leq p, α \leq 10^9$，$p$ 是素数）。 第二行包含整数 $A$ 的十进制表示（$0 \leq A < 10^{1000}$），没有前导零。

输出一行，为问题的答案。

在第一个样例中，有三种二项式系数能被 4 整除，分别是 $\binom{4}{2}$, $\binom{4}{3}$ 和 $\binom{4}{4}$。 由 ChatGPT 5 翻译