CF - 1794d

MateoCV 大佬没有废话，直指答案即为素数选择－－(P_i or P_i-1, 后者有 恰n个)!连乘之倒数之和，再乘上合数选择－－n!/Prod(C_i!)。

求素数选择转化为递推式：f(i,j)=1/P_i! * f(i-1,j) + 1/(P_i-1)! * f(i-1,j-1)。 至此可直接递推平方复杂度处理。

更进一步，可观察到式子其实是卷积的一位，为prod([1/P_i, 1/P_i-1])的第n位。 分治两两乘起＋FFT的复杂度是线性乘对数平方。