#2988. 「CTSC 2016」萨菲克斯 · 阿瑞

内存限制:256 MiB 时间限制:5000 ms 输入文件: suffix.in 输出文件: suffix.out
题目类型:传统 评测方式:文本比较
上传者: YMDragon

题目描述

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

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

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

对于一个字符串 s=s1s2sns=s_1s_2\cdots s_n,记 suf(i)suf(i) 表示 ii 这个位置到末尾的子串。后缀数组为一个 11nn 的排列 p1,p2,,pnp_1, p_2, \cdots , p_n,满足 suf(p1)<suf(p2)<<suf(pn)suf(p_1)<suf(p_2)<\ldots <suf(p_n)。对于两个字符串 sstt,令 ii 为第一个使得 sitis_i \neq t_i 的位置,那么我们称 sis_itit_i 中小的对应的字符串更小,如果 ii 不存在,那么长度小的字符串更小。

对于字符之间的大小关系,我们规定第 11 个字符最小,第 22 个字符次小,依次类推。

输入格式

输入文件为 suffix.in

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

接下来一行, 包含 mm 个非负整数 c1,c2,,cmc_1, c_2, \ldots , c_m,表示每种字符最多的出现次数。保证 0c1,c2,,cmn0 \le c_1, c_2, \ldots , c_m ≤ nc1+c2++cmnc_1 + c_2 + \ldots + c_m \ge n

输出格式

输出文件为 suffix.out

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

样例

样例输入 1

3 2
2 2

样例输出 1

5

样例说明 1

我们记 a 为第一种字符,b 为第二种字符,那么共有 aababaabbbaababbba 这六种可能的字符串。

它们的后缀数组为 (1,2,3)(1,2,3)(3,1,2)(3,1,2)(1,3,2)(1,3,2)(3,2,1)(3,2,1)(2,3,1)(2,3,1)(3,2,1)(3,2,1)。所以共有 55 种不同的结果。

样例输入 2

10 5
2 3 4 3 2

样例输出 2

1003811

样例 3

见附加文件。

数据范围与提示

测试点 nn mm 数据特点
11 6\le 6 6\le 6
2,32,3 10\le 10 10\le 10
44 500\le 500 =2=2
55 500\le 500 =3=3
6,76,7 500\le 500 500\le 500 c1=c2==cm=nc_1=c_2=\ldots =c_m=n
8108\sim 10 50\le 50 50\le 50
111411\sim 14 200\le 200 200\le 200
152015\sim 20 500\le 500 500\le 500