Description

对于一个有 $n(n\ge3)$ 个点和 $m$ 条边的无向简单图，其中点的编号为 $1$ 到 $n$。如果加非负整数条边能使这个图是变为 $n$ 个点的简单环，我们称这个是一个 “半环” 图。

给定两个整数 $n$ 和 $m$，你的任务是计算有多少个不同的 $n$ 个点，$m$ 条边的 “半环” 图。考虑到答案会很大，请将答案模 $10^{9} + 7$ 的结果输出。

定义

• 一个简单图是指一个没有自环和重边的图；
• $n$ 个点的 “简单环” 是指任意一个有 $n$ 个点和 $n$ 条边的无向简单连通图，其中所有点的度均为 $2$；
• 如果两个有着 $n$ 个点和 $m$ 条边的无向简单图是不同的，那么它们具有着不同的边集；
• 现在有两个点 $u$ 和 $v(u < v)$，记 $(u,v)$ 表示连接 $u,v$ 两点的无向边。两条无向边 $(u_1,v_1)$ 和 $(u_2,v_2)$ 如果是不同的，那么 $u_1\ne u_2$ 或 $v_1\ne v_2$。

Input Format

此题有多组数据。

第一行有一个整数 $T$（约为 $2\times 10^{4}$），指测试用例的数量。对于每组数据：

一组数据只有一行，两个整数 $n$ 和 $m$（$3 \le n \le 10^{5}$，$0\le m \le \frac{n(n-1)}{2}$），表示图的点数和边数。

$n$ 的总和不超过 $3\times 10^{7}$。

Output Format

对于每组数据，你只需要输出一行表示答案。

3
4 2
4 3
5 3

15
12
90