包除原理でも解くことができます。 まず、グループを全て区別して考えます。

\(C _ i = M\) で割ったあまりが \(i\) となる人数

とします。このとき、 \(k\) 個以下のグループに分ける方法は、 \(\prod _ {i = 1} ^ {M - 1} \binom{k}{C _ {i}} C_{i}!\) 通りです。

ちょうど \(k\) 個のグループに分ける方法は包除原理を用いて解くことができ、計算量は全体で \(O(N^2 + NM)\) です。