贪吃蛇

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

题目描述

牛牛在玩贪吃蛇，玩贪吃蛇吃掉别的蛇就会变长。牛牛的蛇被别人吃掉后，发现可以看广告复活，且复活后长度不变。

牛牛想到了一个作弊的高招，他和他邀请的 ${n-1}$ 个朋友进入同一个房间玩贪吃蛇，初始时一共有 ${n}$ 条蛇，第 ${i}$ 条蛇的长度为 $L_i$ ，进入游戏后，首先牛牛从这 ${n}$ 条蛇中选择一条蛇作为自己的蛇，然后他的第 ${1}$ 个朋友从剩下的 ${n-1}$ 条蛇中选择一条蛇，然后他的第 ${2}$ 个朋友从剩下的 ${n-2}$ 条蛇中选择一条蛇... ...直到牛牛的第 ${n-1}$ 个朋友选择蛇后，游戏开始，现在他们互相吃掉对方。

设蛇 ${A}$ 此时的长度 $L_A$ ，蛇 ${B}$ 此时的长度 $L_B$ ，蛇 ${A}$ 吃掉蛇 ${B}$ 后蛇 ${A}$ 长度会变为 ${L_A+L_B}$ ，而蛇 ${B}$ 则需要看 ${x}$ 秒广告复活。

牛牛的朋友都会帮助牛牛使牛牛的蛇变得尽可能的长，牛牛想知道， ${M}$ 秒后牛牛的蛇最长可以是多长？

（假设蛇吃蛇不花时间，可以无限次复活，除了吃蛇没有其它方式可以变长，房间里除了牛牛和牛牛的朋友外没有别人）

由于答案可能很大，你只需要输出答案对 ${1e9+7}$ 取模的结果。

输入描述:

输入包含组测试用例，第一行一个整数
每组测试用例第一行三个整数每组测试用例第二行个整数

输出描述:

输出行，第行为第组测试用例的答案。

示例1

输入

复制

输出

复制

2
90
612546

题目描述

输入描述:

输出描述:

输入

输出

备注: