题目描述

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$		无
$5,6$	$10^6$	无	$p$ 为质数
$7,8$	无		无
$9\sim 12$	$10^{18}$	$50$
$13\sim 16$	无	$1000$
$17\sim 20$		$5000$