3283.[GESP202312 八级] 奖品分配

## 题目描述

班上有 $ N $ 名同学，学号从 $ 0 $ 到 $ N-1 $ 。

有 $ M $ 种奖品要分给这些同学，其中，第 $ i $ 种奖品总共有 个 $ a_i $ （ $ i = 0,1,...,M-1 $  ）。

巧合的是，奖品的数量不多不少，每位同学都可以恰好分到一个奖品，且最后剩余的奖品不 超过 $ 1 $ 个（即： $ N \leq a_0 + a_1 + ....+a_{M-1} \leq N+1 $ ）。

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

只要有一位同学获得了不同种类的奖品，即视为不同的方案。

方便起见，你只需要输出方案数对 $ 10^9+7 $ 取模后的结果即可。

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

## 输入格式

第一行一个整数 $ T $ ，表示班级数量。

接下来 $ T $ 行，每行若干用单个空格隔开的正整数。

首先是两个正整数 $ N,M $ ，接着是 $ M $ 个正整数 。

保证 $ N \leq a_0+a_1+...+a_{M-1} \leq N+1 $ 。

## 输出格式

输出 $ T $ 行，每行一个整数，表示该班级分配奖品的方案数对 $ 10^9+7 $ 取模的结果

## 输入
```in1
3
3 2 1 2
3 2 1 3
5 3 3 1 1
```

## 输出
```out1
3
4
20
```

```in2
5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99
```

```out2
1
125970
895031741
307187590
```

## 提示

**样例解释 1**

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

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

对于第 $ 3 $ 个班级，可以把编号为 $ 1 $ 的奖品分配给 $ 5 $ 名同学中的任意一名，共有 $ 5 $ 种方案；再把编号为 $ 2 $ 的奖品分配 给剩余 $ 4 $ 名同学中的任意一名，共有 $ 4 $ 种方案；最后给剩余 $ 3 $ 名同学自然获得 $ 0 $ 号奖品。因此，方案数为 $ 5*4 = 20 $ 。

## 数据范围

对于$ 30\%$ 的测试点，保证 $N\le10$。

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

对于所有测试点，保证 $N\le1000$；保证 $T\le1000$；保证 $M\le1001$。