徽章计数__牛客网

$\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。）

$\hspace{15pt}$ 每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ （ $1 \le T \le 2 \cdot 10^4$ ）代表数据组数，每组测试数据描述如下：

$\hspace{15pt}$ 第一行输入用空格隔开的两个整数 $n$ 和 $m$ （ $1 \le n \le 2 \cdot 10^5$ ； $1 \le m \le 10^9$ ），表示小朋友的数量、徽章图案的数量。
$\hspace{15pt}$ 第二行输入用空格隔开的 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le n$ ），表示恰有 $a_i$ 位小朋友得到的徽章图案与第 $i$ 位小朋友的图案相同（含自身）。

$\hspace{15pt}$ 除此之外，保证单个测试文件的 $n$ 值之和不超过 $2 \cdot 10^5$ 。

徽章计数

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题