题目内容

给定一个长度为$n$ 的正整数序列$a_1,a_2,\dots,a_n$。你必须进行$k$ 次操作（若所有元素均为$1$ 时则无法继续，提前停止，即使你还有剩余操作次数。）：每次选择一个满足$a_i>1$ 的下标$i$，将$a_i$ 减一（$a_i:=a_i-1$）。

在上述前提下，最终序列的乘积$\prod\limits_{i=1}^n a_i$ 尽可能大。输出该最大乘积对$(10^9+7)$ 取模的结果。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T\ (1\le T\le 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入两个整数$n,k\ (1\le n\le 2\times 10^5,\ 0\le k\le 10^{18})$；
• 第二行输入$n$ 个整数，表示序列$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9)$。

保证所有测试中$n$ 的总和不超过$4\times 10^5$。

输出描述

对于每组数据，输出一个整数，操作后可以得到的序列最大乘积对$(10^9+7)$ 取模后的结果。

样例1

输入

3
3 3
2 2 3
4 2
5 1 3 2
1 100
10

输出

2
18
1