[CTSC2016]萨菲克斯·阿瑞

内存限制：256 MB 时间限制：5000 ms

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

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

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

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

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

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

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

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

样例输入 1

3 2
2 2

样例输出 1

样例输入 2

10 5
2 3 4 3 2

样例输出 2

【样例 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 种不同的结果。

【数据范围】

对于前5%的测试点，$n,m≤6$

另有10%的测试点，$n,m≤10$

另有20%的测试点，$n,m≤500$，其中有5%的测试点 $m=2$，5%的测试点 $m=3$，10%的测试点 $c_1=c_2=…c_m=n$

另有15%的测试点，$n,m≤50$

另有20%的测试点，$n,m≤200$

另有30%的测试点，$n,m≤500$

C0100 [CTSC2016]萨菲克斯·阿瑞

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

样例输入 2

样例输出 2

提示