Extended Lucas theorem
中文版本请见这里。
\(\newcommand{\stirlingI}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}\) Lucas theorem is quite well known for compute \(\binom{n}{m} \pmod{p}\):
Let \(p\) be a prime, \(n = u_1 p + u_2\),\(m = v_2 p + v_2\) where \(0 \leq u_2, v_2 < p\), then we have \[ \binom{n}{m} \equiv \binom{u_1}{v_1} \binom{u_2}{v_2} \pmod{p}. \]
However, Lucas theorem only works for prime \(p\). For composites CRT can rescue us, but we still have to solve the hard case where \(p\) is a prime power, which this post mainly discusses. The post borrows a lot from a post by prabowo (although I guess he also references min_25's blogpost), while having its own novelties (mostly the upper bound).
Andrew Granville also has a paper on Extended Lucas theroem. However, there are too many cases in the paper and the overall time complexity is also high. I'd never write it again after I did it once.