先筛出1e6的质数，之后考虑到组合数有阶乘的表达式，第一反应是勒让德定理，但n范围太大，会t。直接考虑阶乘中每个质因子p的贡献，分母减去，分子加上。
值得注意的是，在n-k+1~n中，最终没有被素数表里除掉的数（当然包括除完后大于一的数）一定是大于1e6的质数，因为1e12范围内的n不可能由两个大于1e6的质数相乘组成。最关键的是，剩下的质数两两各不相同。这里可以采用反证法，若两者相等，其原来的数之间至少间隔p，将p开至稍大于1e6，（比如1e6+10），那么p将大于k，矛盾！ 所以最终再将这些质数收集起来即可。