题目内容

有 n 个工厂，第 i 个工厂初始拥有 $a_i$ 台机器。你总共拥有 k 次调整机会。每次调整可以选择一个剩余机器数大于 1 的工厂，将其机器数减少 1。如果所有工厂都只剩 1 台机器，则即使还有剩余调整次数，也必须提前停止。操作结束后，令 $b_i$ 为第 i 个工厂的最终机器数，总产能定义为 $\prod_{i=1}^{n} b_i$。你的目标是使总产能最大，输出最大总产能对 $10^9+7$ 取模后的结果。数据范围：测试组数 $T$ 满足 $1 \le T \le 10^5$；每组中 $1 \le n \le 2 \times 10^5$，$0 \le k \le 10^{18}$，$1 \le a_i \le 10^9$；所有测试数据的 n 总和不超过 $4 \times 10^5$。

输入描述

第一行包含一个整数 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

输入

2
3 1
3 3 3
2 0
4 5

输出

18
20

说明

第一组：三个工厂的机器数均为 3，可调整 1 次。将任意一个工厂减少 1 台机器后，机器数为 $3,3,2$，产能为 $3 \times 3 \times 2 = 18$。这是唯一本质不同的调整方式。

第二组：调整次数为 0，两个工厂保持 $4$ 和 $5$ 台机器，产能为 $4 \times 5 = 20$。

样例2

输入

1
4 5
6 2 6 3

输出

72

说明

四个工厂机器数为 $6,2,6,3$，调整次数 $k=5$。为使产能损失最小，应优先降低当前机器数最多的工厂。

排序后为 $2,3,6,6$。先把两个 6 一起向下压：还差 1 次就能把它们都降到 3，因此在这一层把剩余 5 次分给这两个工厂，得到商 $q=\lfloor 5/2 \rfloor=2$、余数 $r=1$。最终两个较大工厂变为 4 和 3，前面两个工厂保持 2 和 3。

产能为 $2 \times 3 \times 4 \times 3 = 72$。

样例3

输入

3
2 10
3 4
1 0
7
5 3
8 1 1 1 1

输出

1
7
5

说明

第一组：最多可减少 $(3-1)+(4-1)=5$ 台机器，而 $k=10 \ge 5$，所有工厂最终都只剩 1 台机器，答案为 1。

第二组：只有一个工厂且 $k=0$，产能就是初始机器数 7。

第三组：四个工厂已经是 1，只能把机器数为 8 的工厂减少 3 次，变为 5。其余工厂保持 1，产能为 5。

样例4

输入

1
4 6
10 10 10 10

输出

5184

说明

四个工厂机器数已经相等，共调整 6 次。平均每个工厂降低 $q=\lfloor 6/4 \rfloor=1$ 台，余下 $r=2$ 个工厂再多降 1 台。

因此最终有 2 个工厂为 $10-1=9$，有 2 个工厂为 $8$。产能为 $9^2 \times 8^2 = 81 \times 64 = 5184$。