There’s a solution using combinatorics.

First,let’s fix \(k\) and calculate the answer.

We calculate the answer when groups are distinguishable. Let’s call it \(g(k)\). \(\frac{g(k)}{k!}\) is exactly what we want.

Consider \(\{\overline{0},\overline{1},...,\overline{m-1}\}\). It means \(\overline{i}=\{qk+i \mid q\in \mathbb{Z}\land 1\le qk+i\le n\}\)。

Let \(cnt_i:=|\overline{i}|\)，and \(val_i=\dbinom{k}{cnt_i}\)。

\(g(k)\) seems to be \(\prod_{i=0}^{m-1}val_i\) but not. Because some groups may be empty.

Lef \(f(k)\) be the answer when groups are distinguishable and can be empty. And \(f(k)\) will be \(\prod_{i=0}^{m-1}val_i\). So we can calculate all \(f(k)\) in \(O(nm)\).

But how can we calculate \(g(k)\)？We can see that:

\[f(k)=\sum_{i=0}^{k}\dbinom{k}{i}g(i)\]

By binomial inversion ：

\[\Leftrightarrow g(k)=\sum_{i=0}^k(-1)^{k-i}\dbinom{k}{i}f(i)\]

Since we’ve calculated all \(f(i)\). We can easily calculate \(g(k)\) in \(O(n)\) and calculate all \(g(k)\) in \(O(n^2)\).

Implementation https://atcoder.jp/contests/abc217/submissions/25579315