考虑分别计算恰有 $i$ 中颜色恰出现 $S$ 次的方案数，记为 $f_i$，则答案为 $\sum_{i=0}^{m}{f_i w_i}$。

直接算 $f_i$ 不好算，考虑至少有 $i$ 中颜色恰出现 $S$ 次的方案数，记为 $g_i$，显然，

$$g_i = C_{m}^{i} \frac{n!}{(n - iS)! (S!)^i} (m - i)^{n - iS}$$

式子中的三项分别表示： “选出 $i$ 种颜色”，“选位置让这 $i$ 种颜色恰出现 $S$ 次”，“其余的随便填剩下的颜色”。

这个式子是会算重的。具体的，对于一种恰有 $j(j \ge i)$ 种颜色恰出现 $S$ 次的方案，它在 $f_i$ 中会被算 $C_j^i$ 次。于是，

$$g_i = \sum_{j=i}^{m}{C^i_j f_j}$$

根据二项式反演有，

$$f_i = \sum_{j=i}^{m}{C^i_j g_j (-1)^{j-i}}$$

至此我们有了 $O(m^2)$ 的算法。

二项式反演是可以化成卷积形式的，

$$f_i = \sum_{j=i}^{m}{C^i_j g_j (-1)^{j-i}}$$

$$\rightarrow \quad f_i = \frac{1}{i!} \sum_{j=i}^{m}{\frac{j!}{(j-i)!} g_j (-1)^{j-i}}$$

下边懒得打这个 $\frac{1}{i!}$。

令 $A_i = i!g_i \, , \, B_i = \frac{(-1)^{i}}{i!}$ 则，

$$f_i = \sum_{j=i}^{m}{A_{j} B_{j-i}}$$

这里涉及差卷积，令 $A'_i = A_{m-i} \, , \, f'_i = f_{m-i}$ （也就是翻转）则，

$$f'_{m-i} = \sum_{j=i}^{m}{A'_{m-j} B_{j-i}}$$

再令 $t=j-i$ 有，

$$f'_{m-i} = \sum_{t=0}^{m-i}{A'_{m-i-t} B_{t}}$$

也就是，

$$f'_{i} = \sum_{t=0}^{i}{A'_{i-t} B_{t}}$$

这就是标准卷积形式，使用 $NTT$ 即可。$(1004535809=479 \times 2^{21} +1)$

值得注意的是，上述变形没有用到关于 $f_i$ 或 $g_i$ 的性质，于是对任何二项式反演均成立。