F. RUN
SUBTASK 10 PT
对于 10%10\%10% 的数据 n≤5×103n \le 5\times 10^3n≤5×103，直接代入公式暴力递推、枚举即可。
SUBTASK 40 PT
首先化简公式，引入杨辉三角（当然使用 Catalan 数亦可）：
11 11 2 11 3 3 1…1\\ 1\ 1\\ 1\ 2\ 1\\ 1\ 3\ 3\ 1\\ \ldots 11 11 2 11 3 3 1…
杨辉三角的实质是二项式系数的几何排列。若一个人从第一个 111 处走，只能向下或右下，走到该地的方案数。其组合数表示为：
Cnk=n!k!×(n−k)!C_n^k=\frac{n!}{k!\times(n-k)!} Cnk =k!×(n−k)!n!
容易将公式转换为：
∑k=0n(kn)2 mod p\sum_{k=0}^n(_k^n)^2\bmod p k=0∑n (kn )2modp
根据范德蒙德公式化简：
∑k=0n(kn)2 mod p=∑k=0n(n−kn)(kn) mod p\sum_{k=0}^n(_k^n)^2\bmod p\\ =\sum_{k=0}^n(_{n-k}^{n})(_k^n)\bmod p\\ k=0∑n (kn )2modp=k=0∑n (n−kn )(kn )modp
再根据二项式定理化简：
∑k=0n(n−kn)(kn) mod p=(n2n) mod p\sum_{k=0}^n(_{n-k}^{n})(_k^n)\bmod p\\ =(_n^{2n})\bmod p k=0∑n (n−kn )(kn )modp=(n2n )modp
拓展：实际上存在 Vandermonde 恒等式可直接得到：
∑k=0n(kn)2=(n2n)\sum_{k=0}^n(_k^n)^2=(_n^{2n}) k=0∑n (kn )2=(n2n )
两边同时 mod p\bmod pmodp，得：
∑k=0n(kn)2 mod p=(n2n) mod p\sum_{k=0}^n(_k^n)^2 \bmod p=(_n^{2n})\bmod p k=0∑n (kn )2modp=(n2n )modp
由于 p∈Primep \in \operatorname{Prime}p∈Prime，考虑使用 Lucas 定理：
(nk)≡(⌊k/p⌋⌊n/p⌋)(k mod pn mod p)(modp)(_n^k)\equiv(_{\lfloor k/p \rfloor}^{\lfloor n/p \rfloor})(_{k \bmod p}^{n \bmod p})\pmod p (nk )≡(⌊k/p⌋⌊n/p⌋ )(kmodpnmodp )(modp)
其中，当 n<kn<kn<k 时，二项式系数 (nk)(_n^k)(nk ) 规定为 000 。
递归求解即可。
40 PT CODE
时间复杂度：O(p+logpn)O(p+\log_p n)O(p+logp n)
SUBTASK 100 PT
请先阅读 40 pt 做法。
由于 Lucas 定理只能在 ppp 为质数的情况下使用，对于 100%100\%100% 的数据我们考虑扩展 Lucas 定理。
对于 ppp 是一般的合数的情形，只需要首先对它做素因数分解：
p=m1a1m2a2…msasp=m_1^{a_1}m_2^{a_2}\ldots m_s^{a_s} p=m1a1 m2a2 …msas
然后，分别计算出模 miaim_i^{a_i}miai 下组合数 (kn)(_k^n)(kn ) 的余数，就得到 sss 个同余方程：
{(kn)≡r1(modp1a1)(kn)≡r2(modp2a2)…(kn)≡rs(modpsas)\begin{equation} \begin{cases} (_k^n)\equiv r_1\pmod{p_1^{a_1}}\\ (_k^n)\equiv r_2\pmod{p_2^{a_2}}\\ \ldots\\ (_k^n)\equiv r_s\pmod{p_s^{a_s}} \end{cases} \end{equation} ⎩⎨⎧ (kn )≡r1 (modp1a1 )(kn )≡r2 (modp2a2 )…(kn )≡rs (modpsas )
引入中国剩余定理（CRT）：
{x≡a1(modn1)x≡a2(modn2)…x≡ak(modnk)\begin{equation} \begin{cases} x\equiv a_1\pmod{n_1}\\ x\equiv a_2\pmod{n_2}\\ \ldots\\ x\equiv a_k\pmod{n_k} \end{cases} \end{equation} ⎩⎨⎧ x≡a1 (modn1 )x≡a2 (modn2 )…x≡ak (modnk )
利用中国剩余定理（CRT）即可求出模 ppp 的余数。
AC CODE
时间复杂度：O(logn)O(\log n)O(logn)
