UOJ Logo Universal Online Judge

UOJ

#199. 【CTSC2016】萨菲克斯·阿瑞

统计

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

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

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

对于一个字符串 $s=s_1s_2...s_n$,记 $\mathrm{suf}(i)$ 表示 $i$ 这个位置到末尾的子串。后缀数组为一个 $1$ 到 $n$ 的排列 $p_1,p_2,...,p_n$,满足 $\mathrm{suf}(p_1)< \mathrm{suf}(p_2)< \dots < \mathrm{suf}(p_n)$。对于两个字符串 $s$ 和 $t$,令 $i$ 为第一个使得 $s_i \neq t_i$ 的位置,那么我们 $s_i$ 和 $t_i$ 中小的对应的字符串更小,如果 $i$ 不存在,那么长度小的字符串更小。

对于字符串之间的大小关系,我们规定第 $1$ 个字符最小,第 $2$ 个字符次小,以此类推。

输入格式

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

接下来一行,包含 $m$ 个非负整数 $c_1,c_2,...,c_m$,表示每种字符最多的出现次数。保证 $0 \leq c_1,c_2,...,c_m \leq n,c_1+c_2+...+c_m \geq n$。

输出格式

输出共一行,包含一个正数,表示答案。

样例一

input

3 2
2 2

output

5

explanation

我们记 $a$ 为第一种字符,$b$ 为第二种字符,那么共有 $aab,aba,abb,baa,bab,bba$ 这六种可能的字符串。它们的后缀数组为 \begin{equation} (1,2,3),(3,1,2),(1,3,2),(3,2,1),(2,3,1),(3,2,1). \end{equation} 所以共有 $5$ 种不同的结果。

样例二

input

10 5
2 3 4 3 2

output

1003811

样例三

见样例数据下载

限制与约定

测试点编号$n$$m$约定
1$\leq 6$$\leq 6$
2-3$\leq 10$$\leq 10$
4$\leq 500$$=2$
5$=3$
6-7$\leq 500$$c_1=c_2=...=c_m=n$
8-10$\leq 50$$\leq 50$
11-14$\leq 200$$\leq 200$
15-20$\leq 500$$\leq 500$

时间限制:$5\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载