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

[GESP202312八级] 奖品分配

题目描述

班上有 NN 名同学,学号从 00N1N - 1 。有 MM 种奖品要分给这些同学,其中,第 ii 种奖品总共有 aia_{i} 个( i=0,1,,M1i = 0, 1, …, M - 1)。巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不 超过 11 个(即:Na0+a1+...+aM1N+1N \leq a_{0} + a_{1} + ... + a_{M-1} \leq N + 1)。

现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对 109+710^9 + 7 取模后的结果即可。

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

输入格式

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

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

输出格式

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

样例

3
3 2 1 2
3 2 1 3
5 3 3 1 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 个班级,可以把编号为 11 的奖品分配给 55 名同学中的任意一名,共有 55 种方案;再把编号为 22 的奖品分配给剩余 44 名同学中的任意一名,共有 44 种方案;最后给剩余 33 名同学自然获得 00 号奖品。因此,方案数为 54=205 * 4 = 20

数据范围

  • 对于 30%30 \% 的测试点,保证 N10N \leq 10
  • 对于另外 30%30 \% 的测试点,保证 M=2M = 2
  • 对于所有测试点,保证 N1000N \leq 1000 ;保证 T1000T \leq 1000 ;保证 M1001M \leq 1001

来源

GESP 2023年12月 C++八级T1