好的，我们先一步步分析这个组合计数问题。

---

题意整理

• 长度为 (N) 的序列，每个位置可以染 (M) 种颜色之一。
• 对于一种染色方案，统计 恰好出现 (S) 次 的颜色种数，设为 (k)。
• 这种方案的愉悦度是 (W_k)。
• 求 所有 (M^N) 种染色方案 的愉悦度总和，模 (1004535809)（这是一个 NTT 模数，(= 479 \times 2^{21} + 1)，原根 (g=3)）。

---

第一步：重新描述问题

设 (x_i) 表示颜色 (i) 在序列中出现的次数，则
[ x_1 + x_2 + \dots + x_M = N, \quad x_i \ge 0 ] 对于一种颜色，出现次数恰好为 (S) 的概率或计数需用组合数表示。

---

对于染色方案，我们用 序列分配 的观点看：
首先把 (N) 个位置划分给 (M) 种颜色，每种颜色得到 (x_i) 个位置，然后给这些位置上颜色（但相同颜色的位置之间没有区别，因为颜色是给定的种类）。
所以总方案数为： [ \sum_{x_1+\dots+x_M=N} \binom{N}{x_1,x_2,\dots,x_M} = M^N ] 这是已知的恒等式。

---

第二步：按“出现次数恰为 S 的颜色种数”分类

设 (k) 为恰出现 (S) 次的颜色数量，那么

• 有 (k) 种颜色出现 (S) 次，
• 其他 (M-k) 种颜色出现次数 (\ne S)（可以是 (0) 到 (N) 但 (\ne S)）。

我们要计算： [ \text{Ans} = \sum_{k=0}^M W_k \cdot #{\text{染色方案，恰有 (k) 种颜色出现 (S) 次}} ]

---

第三步：计算方案数

我们分两步计数：

1. 从 (M) 种颜色中选出 (k) 种作为“出现 (S) 次”的颜色，共 (\binom{M}{k}) 种选法。
2. 给这 (k) 种颜色每种分配 (S) 个位置，共占 (kS) 个位置。分配方式有 (\frac{N!}{(S!)^k \cdot (N-kS)!})（多重组合数）种。
3. 剩下的 (N-kS) 个位置由剩下的 (M-k) 种颜色去染，但每种不能出现恰好 (S) 次，且这些颜色可以出现 (0) 次。

---

子问题：

给定 (m = M-k) 种颜色，去染 (n = N - kS) 个位置，要求每种颜色出现次数 不能等于 (S)，求染色方案数。

---

第四步：用多项式方法求解子问题

对于一种颜色，它可以占 (0, 1, 2, \dots) 个位置，但不能占 (S) 个位置（这里 (S) 是题目给定的固定值）。
那么对于一种颜色的占位情况，其生成函数为： [ F(z) = \sum_{j \ge 0, j \ne S} \frac{z^j}{j!} = e^z - \frac{z^S}{S!} ] 这是因为如果颜色可任意出现次数，则 EGF 是 (e^z)；减去 (z^S/S!) 就排除了出现 (S) 次的情况。

---

现在有 (m) 种颜色，独立，总占位 EGF 为： [ F(z)^m ] 我们要求的是 (n! \cdot [z^n] F(z)^m)，即把 (n) 个位置分配给这 (m) 种颜色且不违反约束的方案数（注意这是排列数，因为颜色不同）。

所以子问题答案： [ \text{Count}(m, n) = n! \cdot [z^n] \left(e^z - \frac{z^S}{S!}\right)^m ]

---

第五步：代回原问题

原问题中，对于固定的 (k)，方案数： [ \text{Num}(k) = \binom{M}{k} \cdot \frac{N!}{(S!)^k (N-kS)!} \cdot \text{Count}\big(M-k, N-kS\big) ] 其中 (\text{Count}(m, n) = n! \cdot [z^n] \left(e^z - \frac{z^S}{S!}\right)^m)。

注意 (n = N-kS) 必须非负，否则没有方案。所以 (k \le \lfloor N/S \rfloor)。

---

第六步：代入原式

[ \text{Ans} = \sum_{k=0}^{\min(M, \lfloor N/S \rfloor)} W_k \cdot \binom{M}{k} \cdot \frac{N!}{(S!)^k (N-kS)!} \cdot (N-kS)! \cdot \big[z^{N-kS}\big] \left(e^z - \frac{z^S}{S!}\right)^{M-k} ] 化简 ((N-kS)!)： [ \text{Ans} = \sum_{k} W_k \cdot \binom{M}{k} \cdot \frac{N!}{(S!)^k} \cdot \big[z^{N-kS}\big] \left(e^z - \frac{z^S}{S!}\right)^{M-k} ]

---

第七步：变换为卷积形式

令 (n = N-kS)，那么 (N = n + kS)。

我们需要对 (k) 求和，但 (n) 依赖于 (k)，不方便直接卷积。
考虑设 (j = M-k)，则 (k = M-j)，那么 (n = N - (M-j)S)。
注意 (n \ge 0) 且 (j \ge 0)。

这个替换不一定更方便。我们保留原来的 (k) 并设法用多项式展开处理。

---

展开 (\left(e^z - \frac{z^S}{S!}\right)^{M-k})

用二项式定理： [ \left(e^z - \frac{z^S}{S!}\right)^{M-k} = \sum_{t=0}^{M-k} \binom{M-k}{t} e^{tz} \cdot \left(-\frac{z^S}{S!}\right)^{M-k-t} ] [ = \sum_{t=0}^{M-k} (-1)^{M-k-t} \binom{M-k}{t} \frac{z^{S(M-k-t)}}{(S!)^{M-k-t}} e^{tz} ]

我们要提取 ([z^{N-kS}])： 指数是 (S(M-k-t) + \text{幂次来自 } e^{tz}) 展开的任意幂次 (r)（来自 (e^{tz} = \sum_{r\ge0} \frac{(tz)^r}{r!})）。

所以 (z) 的总指数为 (S(M-k-t) + r)，令其等于 (N-kS)： [ S(M-k-t) + r = N - kS ] [ r = N - kS - S(M-k-t) = N - SM + St ] (r) 必须是非负整数。

所以 (t) 要满足 (N - SM + St \ge 0) 且整数，并且 (0 \le t \le M-k)。

这样我们得到： [ [z^{N-kS}] \left(e^z - \frac{z^S}{S!}\right)^{M-k} = \sum_{t} (-1)^{M-k-t} \binom{M-k}{t} \frac{1}{(S!)^{M-k-t}} \cdot \frac{t^{N-SM+St}}{(N-SM+St)!} ] 其中求和范围是 (t \ge \max(0, (SM-N)/S)) 且 (t \le M-k)，且 (N-SM+St \ge 0)（其实 (t \ge \max(0, \lceil (SM-N)/S \rceil ))）。

---

但这会形成三重求和（对 (k, t)），太复杂。我们需要更直接的多项式方法。

---

第八步：标准套路（EGF 与二项式反演）

设 (f_m(n)) 表示 (m) 种颜色染 (n) 个位置，每种颜色出现次数 不等于 (S) 的方案数（EGF 法已得）。

但我们也可以设 (g_m(n)) 表示 (m) 种颜色染 (n) 个位置，没有限制的方案数，显然 (g_m(n) = m^n)。

利用二项式反演：

设 (h_m(n, a)) 表示 (m) 种颜色染 (n) 个位置，恰好有 (a) 种颜色出现 (S) 次 的方案数。
设 (H_m(x) = \sum_{a} h_m(n,a) x^a)。

考虑先选出 (a) 种颜色强制它们各出现 (S) 次，剩下 (m-a) 种颜色任意但不能出现 (S) 次（这不对，因为我们只要求“恰好”这 (a) 种是 (S) 次，其他的可以任意，包括也是 (S) 次，这是二项式反演的来源）。

更标准做法是：
设 (F(y)) 是 EGF（关于颜色种数），对于一种颜色，如果它出现 (S) 次，贡献 (y \cdot \frac{z^S}{S!})；否则贡献 (\frac{z^j}{j!})（(j \ne S)）不带 (y)。

一种颜色的 EGF 为： [ \left(e^z - \frac{z^S}{S!}\right) + y \cdot \frac{z^S}{S!} = e^z + (y-1) \cdot \frac{z^S}{S!} ]

那么 (m) 种颜色的 EGF 为： [ \left(e^z + (y-1) \frac{z^S}{S!}\right)^m ]

系数 ([y^a z^N]) 表示选了 (a) 种颜色出现 (S) 次，且总长度为 (N) 的方案数（未乘以 (N!) 前）。

乘以 (N!) 后得到实际方案数。

所以： [ h_m(N,a) = N! \cdot [z^N y^a] \left(e^z + (y-1) \frac{z^S}{S!}\right)^m ]

展开： [ \left(e^z + (y-1) \frac{z^S}{S!}\right)^m = \sum_{i=0}^m \binom{m}{i} e^{z(m-i)} \cdot \left((y-1)\frac{z^S}{S!}\right)^i ] [ = \sum_{i=0}^m \binom{m}{i} (y-1)^i \frac{z^{S i}}{(S!)^i} e^{z(m-i)} ]

提取 ([z^N])： [ [z^N] z^{S i} e^{z(m-i)} = [z^{N-Si}] e^{z(m-i)} = \frac{(m-i)^{N-Si}}{(N-Si)!} ] 若 (N-Si < 0) 则为 (0)。

因此： [ h_m(N,a) = N! \sum_{i=0}^m \binom{m}{i} [y^a] (y-1)^i \cdot \frac{1}{(S!)^i} \cdot \frac{(m-i)^{N-Si}}{(N-Si)!} ]

注意 ([y^a] (y-1)^i = \binom{i}{a} (-1)^{i-a})。

所以： [ h_m(N,a) = N! \sum_{i=a}^m \binom{m}{i} \binom{i}{a} (-1)^{i-a} \frac{1}{(S!)^i} \cdot \frac{(m-i)^{N-Si}}{(N-Si)!} ]

---

第九步：代入原问题

原问题中 (m = M)，(a = k)，我们要求： [ \text{Ans} = \sum_{k=0}^M W_k \cdot h_M(N,k) ] [ = N! \sum_{k=0}^M W_k \sum_{i=k}^M \binom{M}{i} \binom{i}{k} (-1)^{i-k} \frac{1}{(S!)^i} \cdot \frac{(M-i)^{N-Si}}{(N-Si)!} ]

交换求和顺序，令 (i) 先： [ \text{Ans} = N! \sum_{i=0}^M \binom{M}{i} \frac{1}{(S!)^i} \cdot \frac{(M-i)^{N-Si}}{(N-Si)!} \sum_{k=0}^i W_k \binom{i}{k} (-1)^{i-k} ]

设： [ V_i = \sum_{k=0}^i W_k \binom{i}{k} (-1)^{i-k} ] 那么： [ \text{Ans} = N! \sum_{i=0}^M \binom{M}{i} \frac{1}{(S!)^i} \cdot \frac{(M-i)^{N-Si}}{(N-Si)!} \cdot V_i ]

---

第十步：化简

注意 (N-Si) 必须非负，即 (i \le \lfloor N/S \rfloor)，否则 ((M-i)^{N-Si}) 的指数为负时我们理解为 (0)（因为 (M-i) 为正整数时，负指数无定义；实际上当 (N-Si < 0) 时我们取该项为 0）。

所以上界是 (\min(M, \lfloor N/S \rfloor))。

[ \text{Ans} = \sum_{i=0}^{\min(M, \lfloor N/S \rfloor)} \binom{M}{i} \frac{N!}{(S!)^i (N-Si)!} \cdot (M-i)^{N-Si} \cdot V_i ] 其中 (V_i = \sum_{k=0}^i (-1)^{i-k} \binom{i}{k} W_k)。

---

第十一步：算法实现

1. 已知 (N, M, S) 以及 (W_0, \dots, W_M)。
2. 计算 (V_i) 对 (i = 0,1,\dots,\min(M, \lfloor N/S \rfloor))： [ V_i = \sum_{k=0}^i (-1)^{i-k} \binom{i}{k} W_k ] 这可以看作 (W) 与 ((-1)^k) 的二项式卷积，用一次 NTT 在 (O(M \log M)) 内完成。
3. 对每个 (i) 计算： [ \text{term}_i = \binom{M}{i} \cdot \frac{N!}{(S!)^i (N-Si)!} \cdot (M-i)^{N-Si} \cdot V_i ] 模 (1004535809)。
4. 求和即得答案。

注意阶乘、阶乘逆元、幂次要预处理。

---

复杂度：

• 卷积求 (V_i)：(O(M \log M))
• 求 (\text{term}_i)：(O(M)) 或 (O(N/S))

但 (M \le 10^5)，(N) 可达 (10^7)，计算 ((M-i)^{N-Si}) 需要快速幂，但 (N/S \le N) 可能很大，不过 (M) 较小，所以计算量主要在卷积部分。

---

最终公式： [ \boxed{\text{Ans} = \sum_{i=0}^{\min(M, \lfloor N/S \rfloor)} \binom{M}{i} \frac{N!}{(S!)^i (N-Si)!} (M-i)^{N-Si} \cdot \left( \sum_{k=0}^i (-1)^{i-k} \binom{i}{k} W_k \right) \mod 1004535809} ]

这就是题目的解析与推导结果。