指数型母関数の練習問題です。(指数型母関数については ABC422-G の解説 などを参考にしてください。)

「整数 \(m\) が \(m\) 回以下しか登場しない」ということを頻度に関する母関数 \(F_m(x)\) として表すと

\[F_m(x) = \sum_{i=0}^m \frac{x^i}{i!}\]

となります。求めたいものは

\[\left[ \frac{x^N}{N!} \right] F_1 (x) F_2(x) \dots F_M(x)\]

です。右辺は「多項式同士の畳み込みをして \(N\) 次で打ち切る」という操作を \(M-1\) 回やれば計算できます。畳み込みは \(\mathrm{O}(N^2)\) で計算できるので全体で \(\mathrm{O}(N^2M)\) でこの問題を解くことが出来ます。