解説

本問では制約上、$M$の素因数の指数が$1$と保証されています。
そのため各素因数ごとにLucasの定理で$\binom{N}{R}$ $mod$ $P_i$を計算し、中国剰余定理で解を復元すればよいです。
計算量は前計算$O(M)$・二項係数の計算に$O(logNlogM + logM)$です。
内訳は以下の通りです。

• 階乗の前計算に$O(ΣP_i) \leq O(ΠP_i) = O(M)$時間・空間
• 素因数ごとの二項係数の計算に$O(Σlog_{P_i} N) \leq O(logNlogM)$時間・空間
• 中国剰余定理に$O(Σlog P_i) = O(logM)$時間

なお本問の制約範囲外ですが、抽象化の際には$N,R = 0$や$N < R$、$M = 1$のケースに注意してください。

解答例(Python)

解答例では、二項係数が与えられるたびに階乗を計算しています。