前言
退役之后就开始搞高考了……平时也没有太多时间来思考奇奇怪怪的问题。
本来打算月更的，但是每天做作业做到十二点，计划一下子就赶不上变化了呢……
最近由于学科成绩基本达到了理想，就分一点神来搞搞奇怪的东西吧。（分你一脸神啊！抽代还没看的啊！）
过几周的某场UR过后还会更新一点黑科技的>_<.
今天要写的东西是今年上半年杜教教我的黑科技，当时似乎是另有他用？但是现在这东西好像烂大街了啊……那我就来发表下拙见吧……
问题
给出 ，求：
其中 是个质数。
解决手段
第一种情况：
这个是基本的前置技能了，如果不会的话建议你去膜拜一下福大核武的《组合数取模》那篇文章。
第二种情况：
由于 ，那么我们知道 。现在的关键就是如何来求 .
我们构造一个多项式：
则我们要求的 就是：
注意到 是个 次多项式，并且我们需要将 个值插进去，只需要使用多项式多点求值算法就可以解决了。如果你不会，请看我的博客：多项式除法。
当然，我也不会在模 意义下的FFT，不过我觉得我们可以用 的附加时间，取多个可以用来FFT的模数来运算，最后CRT合并起来。这里由于 一般不超过 ，即最多也只需要6遍不同模数的FFT，我将这部分的复杂度视为
那么总复杂度就是：.
你问我为什么这道题没有出出来？一是因为我自己也写不出来，二是因为……你自己算算 在 时要进行多少运算，又有多少常数……不过我们是理论计算机科学家！
第三种情况：
还残留了一个小问题，不过也不是问题。
相同于核武的做法，我们发现需要用上述算法计算阶乘的过程只有一次，第二次最多不超过计算1000的阶乘。这个就很简单啦。
尾声
如果有人打算拿这个出题，我是不会反对的，你去出吧，我写暴力。
这个题最近真的很多人问我了……莫名地获得了很高的关注度？
下次更新就不知道是什么时候了，那么大家下次见！
