#1269. [GESP202312 八级] 奖品分配

[GESP202312 八级] 奖品分配

题目描述

班上有 NN 名同学,学号从 00N1N-1。有 MM 种奖品要分给这些同学,其中,第 ii 种奖品总共有 aia_i 个 (i=0,1,,M1i=0,1, \cdots ,M-1)。

巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过 11 个(即:Na0+a1++aM1N+1N\le a_0+a_1+ \cdots +a_{M-1}\le N+1)。

现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。

只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对 109+710^{9}+7 取模后的结果即可。

共有 TT 个班级都面临着奖品分配的问题,你需要依次为他们解答。

输入格式

第一行一个整数 TT,表示班级数量。

接下来 TT 行,每行若干用单个空格隔开的正整数。首先是两个正整数N,MN,M,接着是 MM 个正整数 a0,a1...aM1a_0,a_1...a_{M-1}。保证 Na0+a1++aM1N+1N \le a_0+a_1+\cdots+a_{M-1} \le N+1

输出格式

输出 TT 行,每行一个整数,表示该班级分配奖品的方案数对 109+710^{9}+7 取模的结果。

3
3 2 1 2
3 2 1 3
5 3 1 3 1 
3
4
20
5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99
1
1
125970
895031741
307187590

提示

样例解释 1

对于第 11 个班级,学号为 0,1,20,1,2 的同学可以依次分别获得奖品 0,1,10,1,1,也可以依次分别获得奖品 1,0,11,0,1,也可以依次分别获得奖品 1,1,01,1,0 ,因此共有 33 种方案。

对于第 22 个班级,学号为 0,1,20,1,2 的同学可以依次分别获得奖品 0,1,10,1,1 ,也可以依次分别获得奖品 1,0,11,0,1,也可以依次分别获得奖品 1,1,01,1,0,也可以依次分别获得奖品 1,1,11,1,1,因此共有 44 种方案。

对于第 33 个班级,可以把编号为 00 的奖品分配给 55 名同学中的任意一名,共有 55 种方案;再把编号为 22 的奖品分配给剩余 44 名同学中的任意一名,共有44 种方案;最后给剩余 33 名同学自然获得 11 号奖品。因此,方案数为 5×4=205 \times 4 = 20

数据范围

对于 30%30\% 的测试点,保证 N10N \le 10

对于另外 30%30\% 的测试点,保证 M=2M=2

对于所有测试点,保证 N1000N \le 1000;保证 T1000T \le 1000 ;保证 M1001M \le 1001