答えである \(\displaystyle \frac{(C_1 + C_2 + \cdots + C_N)!}{C_1!C_2!\cdots C_N!}\) の計算方法について考えます．

AtCoder でよくある問題の形式では，\(M\) は非常に大きな素数であるため， \(1, 2, 3, \dots, (C_1 + C_2 + \cdots + C_N)\) がいずれも \(M\) と互いに素となり，階乗前計算によって \(O(N)\) 時間で解くことができます．

この問題では互いに素となるとは限りませんが，\(M\) と互いに素である部分とそうでない部分の計算に分けることで，同様に解くことができます．

まず，\(M\) の素因数分解を計算し，\(M = p_1^{c_1} \cdots p_k^{c_k}\) とします．

続いて，答えのうち，\(M\) と互いに素でない部分を計算します．すなわち，各 \(p_i\) について， 「\(\displaystyle \frac{(C_1 + C_2 + \cdots + C_N)!}{C_1!C_2!\cdots C_N!}\) の素因数分解に含まれる \(p_i\) の個数」を求めます．
これは，「各階乗に含まれる \(p_i\) の個数」を前計算しておくことにより，各 \(p_i\) について \(O(N)\) 時間で求めることができます．

その後，答えのうち，\(M\) と互いに素な部分を計算します．すなわち，「\(\displaystyle \frac{(C_1 + C_2 + \cdots + C_N)!}{C_1!C_2!\cdots C_N!}\) を各 \(p_i\) で割れるだけ割った後の値」 \(\text{mod }M\) を計算します．
これは，「各階乗を各 \(p_i\) で割れるだけ割った後の値」 \(\text{mod }M\) を前計算しておくことにより，\(O(N)\) 時間で求めることができます．

全体で \(O(k \cdot (\sum N + \sum C) + \sqrt{M})\) 時間となります． (この問題の制約下で，\(k ≤ 9\) が成り立ちます．)

実装例 (C++)