徽章计数

题号：NC312289
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 在幼儿园里，站有一排 $n$ 位小朋友，而老师 Zaoly 手里有 $m$ 种图案的徽章，每种图案的徽章都有无限多个。Zaoly 会给每位小朋友发放一个徽章。
$\hspace{15pt}$ 小朋友们总有一些奇奇怪怪的要求：有的小朋友希望自己的徽章图案，全班只有他一个人能拥有，这样显得自己的徽章稀缺；有的小朋友希望自己的徽章图案，全班大多数人都能拥有，这样方便与其他同学建立联系。为此，Zaoly 发放徽章时必须保证，对于每个整数 $i$ （ $1 \le i \le n$ ），恰有 $a_i$ 位小朋友得到的徽章图案与第 $i$ 位小朋友的图案相同（这一人数是算上自身的）。

$\hspace{15pt}$ 请你帮 Zaoly 算算，他一共有多少种方法发放徽章？如果有小朋友在两种发放方法中得到了不同图案的徽章，则认为这两种发放方法不同。由于答案可能很大，请将答案对 $10^9 + 7$ 取模。（在此复制：1000000007。）

$\hspace{15pt}$ 用数学语言描述就是：对于给出的长度为 $n$ 的正整数数列 $a_1, a_2, \dots, a_n$ 和正整数 $m$ ，请你计算有多少个长度为 $n$ 的整数数列 $b_1, b_2, \dots, b_n$ 同时满足以下条件：
$\hspace{23pt}\bullet\,$ 对于每个整数 $i$ （ $1 \le i \le n$ ），都有 $1 \le b_i \le m$ 。
$\hspace{23pt}\bullet\,$ 对于每个整数 $i$ （ $1 \le i \le n$ ），恰有 $a_i$ 个整数 $j$ （ $1 \le j \le n$ ）满足 $b_i = b_j$ 。

$\hspace{15pt}$ 由于答案可能很大，请将答案对 $10^9 + 7$ 取模。（在此复制：1000000007。）

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 （）代表数据组数，每组测试数据描述如下：

第一行输入用空格隔开的两个整数  和 （；），表示小朋友的数量、徽章图案的数量。
第二行输入用空格隔开的  个整数 （），表示恰有  位小朋友得到的徽章图案与第  位小朋友的图案相同（含自身）。

除此之外，保证单个测试文件的  值之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示发放徽章的方法数（整数数列的数量），对  取模。

示例1

输入

复制

3
5 10
2 2 3 3 3
2 3
2 1
9 20014
1 1 7 7 7 7 7 7 7

输出

复制

90
0
610066079

说明

对于第二组测试数据，没有方法符合条件，答案为 。

对于第三组测试数据，方法数的真值为 ，取模后得到答案。