RT，此题并不一定需要 Lucas 定理。由于本题保证模数是质数，我们可以预处理阶乘求逆元，在预处理阶乘的时候只计算不等于模数的质因数，把等于模数的质因数直接抠出来放进另一个数组统计即可。

不过总复杂度不是严格 $O(n)$ 的，但是其实速度差不多？（话说 Lucas 的做法也不是 $O(n)$ 的来着