级数

给定非负整数 $n, k$ 和质数 $p$，定义函数

$$f(x) = \sum_{i=0}^{k} \frac{x^{\underline{i}}}{x!\,(n-x)!}$$

其中 $x^{\underline{i}}$ 表示 $x$ 的 $i$ 次下降幂，即

$$x^{\underline{i}} = x(x-1)(x-2)\cdots(x-i+1) \quad (i \ge 1), \qquad x^{\underline{0}} = 1$$

请计算前缀和

$$S(n) = \sum_{x=0}^{n} f(x)$$

在模 $p$ 意义下的值。

输入格式

一行三个整数 $n, k, p$。

输出格式

输出一个整数，表示 $S(n) \bmod p$ 的值。

可以证明 $S(n)$ 是一个有理数且其最简分数的分母与 $p$ 互质。若 $S(n)$ 的最简分数表示为 $\frac{a}{b}$，你需要输出整数 $x \in [0, p)$ 使得 $b \cdot x \equiv a \pmod{p}$。

样例 1

输入

2 1 998244353

输出

4

说明

• $f(0) = \dfrac{1}{0!\cdot 2!} + \dfrac{0}{0!\cdot 2!} = \dfrac{1}{2}$
• $f(1) = \dfrac{1}{1!\cdot 1!} + \dfrac{1}{1!\cdot 1!} = 2$
• $f(2) = \dfrac{1}{2!\cdot 0!} + \dfrac{2}{2!\cdot 0!} = \dfrac{3}{2}$

所以 $S(2) = \dfrac{1}{2} + 2 + \dfrac{3}{2} = 4$，输出 $4 \bmod 998244353 = 4$。

样例 2

输入

3 0 7

输出

6

说明

当 $k = 0$ 时，$f(x) = \dfrac{1}{x!\,(n-x)!}$。

$S(3) = \dfrac{1}{6} + \dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{6} = \dfrac{4}{3}$。

$\dfrac{4}{3} \bmod 7$：因为 $3^{-1} \equiv 5 \pmod{7}$，所以答案为 $4 \times 5 \bmod 7 = 6$。

提示

本题共 $20$ 组数据。

对于前 $20\%$ 的数据，$0 \le k \le n \le 2000$。

对于前 $40\%$ 的数据，$0 \le k \le n \le 2 \times 10^5$。

另有 $20\%$ 的数据，$k = 0$。

另有 $20\%$ 的数据，$k = 1$。

对于 $100\%$ 的数据，$0 \le k \le n \le 5 \times 10^7$，$p$ 为质数且 $n < p \le 10^9 + 7$。