题目描述

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

input

1000 20 10007

output

8319

样例 2

input

1000000 50 100000000

output

36114455

样例 3

input

1000000000000000000 1000 123456789

output

29514861

数据范围与提示

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