题解：某不科学的下降阶乘与二项式求和¶

Codex（GPT-6）：应用下降阶乘恒等式，使用固定模数的阶乘检查点实现求值，并补充常数空间的 Wilson 补集方案。恒等式、费马小定理与 Wilson 定理均为已有数学方法。

组合恒等式¶

从 \(n\) 个物品中先选一个子集，再从中按顺序选出 \(k\) 件指定物品。如果子集大小为 \(i\) ，方案数为 \(\binom ni i^{\underline{k}}\) .

也可以先从全部物品中选出有顺序的 \(k\) 件，有 \(n^{\underline{k}}\) 种方式；其余 \(n-k\) 件独立决定是否进入子集，各有两种选择。这两种顺序描述同一组对象，因此当 \(k\le n\) 时

\[ \sum_{i=1}^{n}\binom ni i^{\underline{k}}=n^{\underline{k}}2^{n-k} \]

当 \(k>n\) 时，每项都为零。题目保证 \(k\ge1\) ，所以不需要补入 \(i=0\) 项。

因为 \(n<P\) ，所有需要的阶乘均非零，故

\[ n^{\underline{k}}=\frac{n!}{(n-k)!}\pmod P \]

取块长 \(B=10^6\) ，保存 \(F_j=(jB)!\bmod P\) ，包括零阶乘。计算任意 \(x!\) 时，从 \(F_{\lfloor x/B\rfloor}\) 开始，再乘当前块中的剩余因子，最多 \(B-1\) 次。逆元使用费马小定理 \(a^{-1}=a^{P-2}\) .

检查点表是固定模数的计算资源，不是任意输入答案表。生成程序依次乘入全部因子，每到块边界输出一个常量，并检查 \((P-1)!\equiv-1\pmod P\) .它可以完全重建头文件。

生成全部检查点需要离线 \(O(P)\) 时间、\(O(P/B)\) 输出空间。单次输入的在线时间为 \(O(B+\log P)\) ，表空间为 \(O(P/B)\) .这项离线代价不能算作零；本方案适用于题目固定模数及给定上界，不声称能同样快速处理任意新模数。

检查点由阶乘递推得到。块内继续乘剩余整数得到精确阶乘；分母可逆，费马求逆得到下降阶乘；乘以 \(2^{n-k}\) 后由组合恒等式得到所求值。所有模乘使用 64 位整数，中间值小于 \(P^2\) .

标准程序选择检查点法，以缩短最大规模的在线计算。常数空间方案及其程序不存储检查点，对较短乘积很方便，空间更少；中间长度的乘积耗时较多，属于完整时限之外的取舍方案。两者在正式文件上输出一致，适用时间范围见性能记录。

验证包含小范围逐项原式求和、随机短乘积、每一百万项区间按反方向重算的表校验程序，以及 Wilson 尾段核验。参见生成与验证说明。