[AdditionalFile6575.zip](file://AdditionalFile6575.zip?type=additional_file)

#6575. LJJ 学二项式定理 · 二

标签: 传统 | 时间限制: 1500 ms | 内存限制: 512 MiB |

题目描述

LJJ 学完了二项式定理，觉得这式子不够优美，于是他随手写下了一个他认为优美的式子：

$$\begin {aligned} \left(\sum_{i=0}^{\left\lfloor \frac{n}{m-1}\right\rfloor } {n+i\choose m\cdot i}\right) \bmod p \end{aligned}$$

其中 $n\choose i$ 表示 $\cfrac{n!}{i!(n-i)!}$。

然而他并不会计算这个式子。你能帮帮他吗？

输入格式

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

输出格式

输出仅一行：一个整数 $\text{ans}$ 表示将 $n, m, p$ 的值代入式子得到的答案。

样例 1

输入

1000 20 10007

输出

8319

样例 2

输入

1000000 50 100000000

输出

36114455

样例 3

输入

1000000000000000000 1000 123456789

输出

29514861

数据范围与提示

对于所有数据，均满足：$n\ge 1,\ 1<m\le n+1,\ p\le 10^9$。

测试点编号	$n\le$	$m\le$	特殊性质
$1\sim 4$	$1000$	$1000$	无
$5,6$	$10^6$		$p$ 为质数
$7,8$			无
$9\sim 12$	$10^{18}$	$50$
$13\sim 16$		$1000$
$17\sim 20$		$5000$	$p = 998244353$