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

LJJ 学二项式定理 · 二

题目描述

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} $$

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

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

输入格式

一行三个整数 n,m,pn, m, p

输出格式

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

样例 1

1000 20 10007
8319
1000000 50 100000000
36114455
1000000000000000000 1000 123456789
29514861

数据范围与提示

对于所有数据,均满足:n1, 1<mn+1, p109n\ge 1,\ 1<m\le n+1,\ p\le 10^9

测试点编号 nn\le mm\le 特殊性质
141\sim 4 10001000 10001000
5,65,6 10610^6 pp 为质数
7,87,8
9129\sim 12 101810^{18} 5050
131613\sim 16 10001000
172017\sim 20 50005000 p=998244353p = 998244353