\(M\)で割った余りが同じ人をひとまとまりにして，次のようなdpを考えます。
\(dp _ {i,j}:= M\)で割ったあまりが\(i-1\)の人たちまで追加し，現在存在するグループの個数が\(j\)の時の場合の数
ただし，\(dp_{0,0}=1,dp_{0,i}=0( i > 0)\)とします。
答えは\(dp_{M,i} \left( 1 \leq i \leq N \right)\)です。

\(f(i)\)を\(M\)で割ったあまりが\(i\)である人の数とします。
\(dp_{i,j}\)からの遷移を考えましょう。
新しく追加されるグループの個数を\(k\)とします。 同じグループに余りが同じである人は入れないことを踏まえて，新しいグループに入れる人を選ぶ\( \binom{f(i)}{k}\)通りと，それ以外の人を現在存在するグループに割り振る\( {}_{f(i)-k}P_{j} \)通りを考え，\(dp_{i+1,j+k}\)に\(dp_{i,j} \binom{f(i)}{k} {}_{f(i)-k}P_{j}\)を足し合わせればよいです。

状態数は\(O(NM)\)で，\(f(i)=O( \frac{N}{M})\)であることから遷移の計算量は\(O( \frac{N}{M} )\)です。結局全体の計算量は\(O(NM)O( \frac{N}{M} )=O(N^{2})\)であることがわかりました。よってこの問題を \(O(N^2)\)で解くことができました。