2306. [CTSC 2016]萨菲克斯·阿瑞

【题目描述】

小P来到了 NOIP2044的赛场上，他发现第二题的题目是这样的：给你一个长度为 n 的字符串，该字符串由至多 m 种不同的字符组成，其中第 i 种字符出现次数不超过 ci，问你这个字符串的后缀数组是什么。

   聪明的小P想到了一个新的问题希望你来帮忙解答：在题目给定的限制下，能有多少种不同的答案。也就是所有由 m 种字符组成，其中第 i 种字符出现次数不超过 ci，且长度为 n 的字符串，共有多少种不同的后缀数组。

   由于答案很大，你只用输出答案对10^9+7取模后的数。

   对于一个字符串 s = s1s2s3 … sn，记 suf(i) 表示 i 这个位置到末尾的子串。后缀数组为一个 1 到 n 的排列 p1,p2,…,pn，满足suf(p1) < suf(p2) < … < suf(pn)。对于两个字符串 s 和 t，令 i 为第一个使得 si≠ ti 的位置，那么我们 si 和 ti 中小的对应的字符串更小，如果 i 不存在，那么长度小的字符串更小。

   对于字符之间的大小关系，我们规定第 1 个字符最小，第 2 个字符次小，依次类推。

【输入格式】

输入的第一行包含 2 个正整数 n,m，表示字符串的长度为 n，共有 m 种字符。

 接下来一行，包含 m 个非负整数 c1,c2,…,cm，表示每种字符最多的出现次数。保证 0 ≤ c1,c2,…,cm ≤ n，c1 + c2 + … + cm ≥n。

【输出格式】

输出共 1 行，包含一个整数，表示答案。

【样例输入1】

3 2
2 2

【样例输出1】

5

【样例输入2】

1O 5
2 3 4 3 2

【样例输出2】

l438522

【提示】

样例1说明:

   我们记 a 为第一种字符，b 为第二种字符，那么共有 aab，aba，abb，baa，bab，bba这六种可能的字符串。它们的后缀数组为（1,2,3），（3,1,2），（1,3,2），（3,2,1）,（2,3,1），（3,2,1）。

   所以共有5种不同的结果。

【来源】

CTSC2016 D1T2