【题意】

求$C^{j}_ {i} \mod p^{k}==0$ 的个数（ $1 \le i \le n,0 \le j \le i$ ）因为答案可能非常大，对 $10^9+7$ 取模。

【输入格式】

一行三个整数 $n ,p ,k \ ( 1 \le n \le 10^{1000} , 1 \le p \le 10^9 , 1 \le k \le 10^9 )$，输入数据保证 $p$ 为质数。

【输出格式】

输出一行答案

4 2 2

2

【样例解释】

$p^k=4$

$C^j_{1 \dots 3}$ 都不整除4

$C^1_4 = 4$ 整除4

$C^3_4 =4$ 整除4

$C_4^0、C_4^2、C_4^4$ 都不整除4

所以有2种情况