小 P 来到了 NOIP2044 的赛场上，他发现第二题的题目是这样的：给你一个长度为 $n$ 的字符串，该字符串由至多 $m$ 种不同的字符组成，其中第 $i$ 种字符的出现次数不超过 $c_i$，问你这个字符串的后缀数组是什么。
聪明的小 P 想到了一个新的问题希望你来帮忙解答：在题目给定的限制下，能有多少种不同的答案。也就是所有由 $m$ 种字符组成，其中第 $i$ 种字符出现次数不超过 $c_i$，且长度为 $n$ 的字符串，共有多少种不同的后缀数组。
由于答案很大，你只用输出答案对 $10^9 + 7$ 取模后的值。
对于字符串之间的大小关系，我们规定第 $1$ 个字符最小，第 $2$ 个字符次小，以此类推。
第一行包含两个正整数 $n, m$ ($n, m \leq 500$)，表示字符串的长度为 $n$，共有 $m$ 种字符。
第二行包含 $m$ 个非负整数 $c_1, c_2, \cdots, c_m$ ($0 \leq c_i \leq m; \sum c_i \geq m$)，表示每种字符最多的出现次数。
输出一行一个整数，表示不同后缀数组的个数模 $10^9 + 7$ 的值。
我们先来探究对于一个给定的后缀数组 (显然它是个排列)，什么情况下它是合法的。
设 SA 中某相邻两个位置分别为 $p_i$ 和 $p_{i+1}$，则一定有 $s \left[ p_i .. \right] < s \left[ p_{i+1} .. \right]$。
显然 $s_{p_i} \leq s_{p_{i+1}}$。考虑何时 $s_{p_i}$ 和 $s_{p_{i+1}}$ 可以相等。假设它们相等，则必有 $s \left[ p_i + 1 .. \right] < s \left[ p_{i+1} + 1 .. \right]$。
(ps: 如果此时 $p_{i+1} = n$，则 $p_{i+1} + 1$ 应该为空。为了避免这种讨论，我们在字符串末尾加上一个字典序最小的串 (如 \x01)，则它的排名应为 $0$，即 SA[0] = n + 1)
从而，在后缀数组中，$p_i + 1$ 也必须在 $p_{i+1} + 1$ 的前面。
也就是说，如果 $p_i + 1$ 在 $p_{i+1} + 1$ 的后面，则 $s_{p_i} < s_{p_{i+1}}$；如果 $p_i + 1$ 也在 $p_{i+1} + 1$ 的前面，则要有 $s_{p_i} \leq s_{p_{i+1}}$。
反过来同样也可以证明，这个条件也是充分的：即如果 $s_i$ 满足上面的绿色条件，则 $p_i$ 的的确确就是 $s_i$ 的后缀数组。
更进一步，我们要知道，怎样的后缀数组 (以下 "后缀数组" 默认指的是后缀数组排列，不是某个特定的串的后缀数组) 是满足题目条件的。
考察任意一个排列。由绿色结论，可知，所有这些 $s_i$ 按顺序会得到一条形如 $s_{p_1} \otimes s_{p_2} \otimes \cdots \otimes s_{p_n}$ 的不等式链，其中 $\otimes$ 为 $\leq $ 或 $<$。
如：后缀数组 5 3 1 4 2 对应的不等式链即为 $s_5 \leq s_3 \leq s_1 < s_4 \leq s_2$ (其实这个 SA 实际上应该是 (6)5 3 1 4 2)，的确，UOJ 的样例 $\texttt {ababa}$ 也满足这个条件。
而题目的限制是，形如 "字典序第 $k$ 小的字符不能超过 $c_k$ 次" 的命题。因此，容易想到使用贪心算法，按照不等式链的顺序从前到后填充字符串，如果超过次数了或者遇到 "$<$" 了就换一个字符，如果能填完说明满足条件，不能填完则说明无法满足。
还是刚才的例子，设字典序第 $k$ 小的字符为第 $k$ 个小写拉丁字母。则 5 3 1 4 2 按照所得的不等式链进行填充，所得到的串为 $\texttt {ababa}$，这恰好就是 UOJ 的样例。
又如，后缀数组 2 1 3 (实际上是 (4)2 1 3) 所对应的不等式链为 $s_2 < s_1 < s_3$，这也是 "不存在字符集大小为 $2$ 的串满足其后缀数组为 2 1 3" 的原因。
接下来我们要开始我们的数数(树)之旅了。
我们从最简单的情形开始着手：$m = 2$。即字符集大小为 $2$。
为了防止计算重复，方便起见，我们对于一个后缀数组 $sa$，定义它的秩为最小的 $m$，满足存在字符集大小为 $m$ 的字符串，使其后缀数组恰好为 $sa$。
可以看出，一个后缀数组的秩等于它在 Part 2 的不等式链中 "$<$" 号的个数。
如，后缀数组 5 3 1 4 2 的秩为 $2$，后缀数组 2 1 3 的秩为 $3$，后缀数组 7 6 5 4 3 2 1 的秩为 $1$。
后缀数组的秩有一些非常好玩但没什么卵用的性质：长度为 $n$ 的后缀数组中，秩为 $1$ 和 $n$ 的后缀数组恰有 $1$ 个。
接下来进入正题。我们需要统计字符集大小为 $2$ 的 SA 的个数，不妨先来统计秩为 $2$ 的 SA 的个数。
设字符串中有 $A$ 个 a，$B$ 个 b。因此将它们进行带重复元素的排列，可知共有 $\dbinom {A + B} A$ 种情况。
我们要从中去掉秩为 $1$ 的情况。由上面 "好玩但没卵用" 的性质，恰有 $1$ 个秩为 $1$ 的后缀数组 (其实就是 $\left[ n, n - 1, n - 2, \cdots, 3, 2, 1 \right]$)，因此由 $A$ 个 a，$B$ 个 b 构成的字符串中，秩为 $2$ 的后缀数组的个数就是 $\dbinom {A + B} A - 1$。
没了？没了。
$m = 2$ 的情况过于特殊了，我们再来看看 $m = 3$ 的情况。
还是统计秩为 $3$ 的后缀数组个数。设其中有 $A$ 个 a，$B$ 个 b 以及 $C$ 个 c。
由可重排列，由这些元素构成的秩不超过 $3$ 的不同 SA 个数共有 $\dbinom {A + B + C} {A, B, C}$ 个。
当然，这些是秩不超过 $3$ 的。我们还是要将这些秩过小的排列 "容斥" 掉。
回到 Part 2 中的不等式链 (非常重要的工具！)。首先，由于这些 SA 的秩不超过 $3$，因此不等式链中严格小于号 "$<$" 的个数不会超过 $2$。
考察 $\dbinom {A + B + C} {A, B, C}$ 个排列中的一个排列 $p$，设它的秩为 $2$。由于它是我们在统计秩为 $3$ 的排列中计入的，因此它的不等式链的形式本应该是：
$$ x_1 \leq x_2 \leq \cdots \leq x_A \color{red} < x_{A + 1} \leq x_{A + 2} \leq \cdots \leq x_{A + B} \color{blue} < x_{A + B + 1} \leq x_{A + B + 2} \leq \cdots \leq x_{A + B + C} \tag 1 \label 1 $$
而事实上，它的秩可以是 $2$。也就是说，实际上，不等式链中只有 $1$ 个严格小于号。
然而 $\eqref 1$ 式中的等号是必定取等的，因此这个唯一的小于号要么在红色位置，要么在蓝色位置。
不妨设 "$<$" 号在蓝色位置，则红色位置上的 $\leq$ 就可以取等了。
也就是说，此时，这个后缀数组即为满足 $s_{p_1} = s_{p_2} = \cdots = s_{p_{A + B}} = \texttt a, \ s_{p_{A + B + 1}} = s_{p_{A + B + 2}} = \cdots = s_{p_{A + B + C}} = \texttt b$ 的串 $s$ 的后缀数组。
也就是说，每个 "由 $A + B$ 个 $\texttt a$，$C$ 个 $\texttt b$ 构成的串" 的后缀数组，都会对我们的统计造成一个 "误判"。因此，我们要答案减去 $\dbinom {A + B + C} {A + B, C}$。
同理，"$<$" 也可以在红色位置，此时则需要减去 $\dbinom {A + B + C} {A, B + C}$。
可以看出，这是一个容斥的过程。聪明的同学应该已经发现，这是一个容斥的过程。于是，我们把秩为 $1$ 的后缀数组 "多减了"，再将其补回来。此时，我们不再在式子中写 $1$ (恰有 $1$ 个秩为 $1$ 的后缀数组)，而是：
$$ tot = \binom {A + B + C} {A, B, C} - \binom {A + B + C} {A + B, C} - \binom {A + B + C} {A, B + C} + \binom {A + B + C} {A + B + C} \tag 2 \label 2 $$
啊，美妙的容斥原理！
然鹅，题目不是让你统计秩为 $m$ 的 SA 的个数，因此我们要进行一些小小的转化。
考虑我们为什么要定义后缀数组的秩。无非就是为了使计算不重复呗！
对，我们刚才所做的那么多就是为了构造一个一一对应，将一个排列对应到一个串上去，使得计数不重不漏。
因此，对于一个排列 $p$，设它的秩为 $r$。我们就应当在统计秩为 $r$ 为排列中统计进去！
那怎么实现呢？枚举 $r$？枚举 $A, B, C$？
冷静一下，当然不是这样的。回到此题最初的形态。我们按字典序从小到大枚举每个字符出现了几次，然后算出有多少个 "满秩" 的后缀数组。(这里 "满秩" 的意思是，这个串的字符集大小恰好等于该后缀数组的秩，不出现字符集冗余的情况)
但是这里还有一个问题。有的秩比较小的后缀数组，它的来源是一个较大的字符集，而它所对应的 "满秩" 的字符串是不符合题目要求的。
举个例子，你有 $2$ 个 $\texttt a$ 和 $2$ 个 $\texttt b$，则 $\texttt {baa}$ 的后缀数组为 $\left[ 3, 2, 1 \right]$，秩为 $1$ (两个不等号都是非严格的，且 $\texttt {aaa}$ 就是字符集大小为 $1$ 的串)，而所对应的 "满秩" 字符串 $\texttt {aaa}$ 或 $\texttt {bbb}$ 均不满足题目要求 (任意字符你只有 $2$ 个)。
不过不用慌，我们可以考虑 "合并" 操作。
考虑 $c_1, c_2, \cdots, c_m$ 从小到大填充的过程。如果一个字符，比如 $\texttt a$，出现了超过 $c_1$ 次。首先，它肯定达到了 $c_1$ 次。因此，一旦它达到了 $c_1$ 次，我们就可以将 $\texttt b$ 的 $c_2$ 次使用机会全都 "借" 给 $\texttt a$ (反正也是有借无还嘛)，从而完成 "合并" 的过程。
当然，如果你 $\texttt a$ 自己的 $c_1$ 次都没用完，就像偷偷用人家 $\texttt b$ 的使用机会。hmhmhm，那你 $\texttt a$ 就是个不道德的串啦。(开个玩笑啦~)
总之，不仅是 $\texttt a$，我们对待每个字符都是公平的 (一视同仁)，只有把你自己的机会用完了，才能使用下一个字符。
(都 Part 6 了，啥时候能讲完啊？) (你先看看首页上的难度再说)
最后就是实现啦。如何高效的完成这个过程？
首先考虑这个容斥的过程。将 $\eqref 2$ 式推广，设第 $i$ 小的字符有 $A_i$ 个。则整个容斥的过程可以看成枚举断点集合 ("$<$" 集合) $\left\{ z_1, z_2, \cdots, z_k = m \right\}$，则这一部分的贡献为
$$ (-1)^{m - k} \binom {A_1 + A_2 + \cdots + A_m} {A_1 + A_2 + \cdots + A_{z_1}, A_{z_1 + 1} + \cdots + A_{z_2}, \cdots, A_{z_{k-1} + 1} + \cdots + A_{z_k}} \tag 3 \label 3 $$
(注：如果公式挂了可以右键公式 -> Math Settings(数学设置) -> Math Renderer(数学渲染) -> 换一个，如 SVG)
像 [uoj214]合唱队形 一样，我们使用 DP 来求解容斥系数。
首先，分子上的 $\left( A_1 + A_2 + \cdots + A_m \right)! = n!$ 是常量，可以预先提出来。
然后就是枚举每个段，设段长为 $len$，则就要乘以它的阶乘倒数 $\dfrac 1 {len!}$。
于是我们就可以设计 DP 方程啦！
用 $f_{i, j, k}$ 表示当前从小到大填充到第 $i$ 个字符，已经填充了 $j$ 个位置 (i.e. 当前 $A$ 的前缀和为 $j$)，最后一段的大小为 $k$ (i.e. $A.\mathrm{back}() = k$)，所得到的容斥系数。
注意，这个 DP 是基于贪心的，因此每个字符一定是能用则用，因此不使用的字符一定是一段后缀，即一旦一个字符未使用，就预示着这个串的 "终结"。
(什么？你说 $c_i = 0$？DP 前先把它们扔了再说)
边界自然就是 $f_{0, 0, 0} = 1$ 啦 (当然如果你愿意把这个 $n!$ 放进来也是可以滴)。
考虑转移，分为三种情况：
第 $i$ 个字符使用若干 (正整数) 个，然后将这一段切掉 (也是最正常的情况)。
设这种字符使用了 $l$ 个，则转移为 $$ f_{i + 1, j + l, 0} \uparrow f_{i, j, k} \cdot \frac 1 {(k + l)!} \tag 4 \label 4 $$
第 $i$ 个字符准备和下一个字符进行容斥型合并，即它们在 $\eqref 3$ 式中使用加号产生贡献。
由于是容斥型合并，每多一个 "$+$" 号就要产生 $-1$ 的系数。故转移方程为 $$ f_{i, j + l, k + l} \uparrow - f_{i, j, k} \tag 5 \label 5 $$
第 $i$ 个字符准备和下一个字符进行正常合并 (即统计秩比较小的后缀数组)。由 Part 5，此时要求第 $i$ 个字符必须用满。
因此转移系数还是 $+1$，方程为 $$ f_{i, j + c_i, k + c_i} \uparrow f_{i, j, k} \tag 6 \label 6 $$
以上 $a \uparrow b$ 表示 a += b (in C++)。
聪明的同学可能早就发现，(在基于 DP 优化的角度下) 第 2 种转移和第 3 种转移可以合并。
其实就相当于，对所有 $1 \leq l \color{red} < a_i$，作第 2 种转移即可。但要注意，这两种转移的实质是不同的，只是可以优化到一起罢了。当然，如果有更好的组合解释可以提出来哦！
至于最后的计算答案，相当于统计这个串在哪个字符处 "终结"，即答案等于 $\displaystyle \sum_{i=1}^m f_{i, n, 0}$。
状态数 $O \left( n^2 m \right)$，总时间 $O \left( n^3 m \right)$。
然鹅这还是过不去，因为 $500$ 的 $O \left( n^4 \right)$ 是挺慢的吧。(指令集优化？)
注意到复杂度中一个 $n$ 是来自转移的，状态数只有 $O \left( n^2 m \right)$。因此我们考虑优化转移复杂度，争取做到 $O(1)$ 转移。
考虑 $\eqref 4$ 式，注意到固定 $j' = j + l, k' = k + l$ 时，$\eqref 4 \Leftrightarrow$
$$ f_{i, j', 0} = \sum_l f_{i, j' - l, k' - l} \cdot \frac 1 {k'!} = \frac 1 {k'!} \cdot \sum_l f_{i, j' - l, k' - l} \tag 7 \label 7 $$
可以发现，将 $f_i$ 看成一个矩阵后，右端的和式就是一个对角线方向的前缀和！
同理，对于 $\eqref 5, \eqref 6$ 两式，固定 $j' = j + l, k' = k + l$ 后，转移的形式 $$ f_{i, j', k'} = - \sum_l f_{i, j' - l, k' - l} \tag 8 \label 8 $$ 也是关于对角线方向的前缀和，不过要注意求和的上下限问题。
因此，我们对这个 DP 进行前缀和优化，即按对角线方向统计前缀和并转移，于是就可以做到单点转移 $O(1)$，
于是，我们可以在 $O \left( n^2 m \right)$ 的时间内解决了这个问题，从而，可以轻松地通过了。
#include <bits/stdc++.h>
#define jl j
#define kl k
typedef long long ll;
const int N = 540, mod = 1000000007;
int n, m;
int c[N], fact[N], finv[N];
int f[N][N], F[N][N];
inline void add(int &x, const int y) {x = (x + y >= mod ? x + y - mod : x + y);}
ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}
int main() {
int i, j, k, l; ll ans = 0;
scanf("%d%d", &n, &m);
for (i = 1; i <= m; ++i) if (scanf("%d", c + i), !c[i]) --i, --m;
for (*fact = i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
finv[n] = PowerMod(fact[n], mod - 2);
for (i = n; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
for (**f = i = 1; i <= m; ++i) {
for (j = 0; j <= n; ++j)
for (k = 0; k <= j; ++k)
add(F[j + 1][k + 1] = F[j][k], f[j][k] + (f[j][k] >> 31 & mod)), f[j][k] = 0;
for (jl = 1; jl <= n; ++jl)
for (kl = 1; kl <= jl; ++kl) {
l = std::min(c[i], kl);
f[jl][0] = (f[jl][0] + (ll)finv[kl] * (F[jl][kl] - F[jl - l][kl - l])) % mod;
if (jl != n) {
l = std::min(c[i] - 1, kl),
f[jl][kl] = ((ll)f[jl][kl] - F[jl][kl] + F[jl - l][kl - l]) % mod;
}
}
ans += f[n][0];
}
ans = ans % mod * fact[n] % mod;
printf("%lld\n", ans + (ans >> 63 & mod));
return 0;
}
坑1：对于 $c_i = 0$ 的情形，要将它们先去掉，再进行转移，否则会被这个字符卡死而无法转移。
坑2：注意使用 (优化取模的) add 函数时需要确保所有变量都是非负的。