给定一个具有 $n$ ($n \ge 3$) 个顶点和 $m$ 条边的无向简单图，其中顶点编号从 $1$ 到 $n$。如果可以通过添加非负数量的边，将其转化为恰好包含 $n$ 个顶点的简单环，则称其为“子环”图。

给定两个整数 $n$ 和 $m$，你的任务是计算具有 $n$ 个顶点和 $m$ 条边的不同子环图的数量。由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

回顾： 简单图是指没有自环或重边的图； $n$ ($n \ge 3$) 个顶点的简单环是一个连通的无向简单图，具有 $n$ 个顶点和 $n$ 条边，其中每个顶点的度数等于 $2$； 两个具有 $n$ 个顶点和 $m$ 条边的无向简单图是不同的，当且仅当它们的边集不同； 设 $u < v$，我们用 $(u, v)$ 表示连接顶点 $u$ 和 $v$ 的无向边。两个无向边 $(u_1, v_1)$ 和 $(u_2, v_2)$ 是不同的，当且仅当 $u_1 \neq u_2$ 或 $v_1 \neq v_2$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($T \approx 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$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示具有 $n$ 个顶点和 $m$ 条边的不同子环图的数量，对 $10^9 + 7$ 取模。

样例

输入 1

3
4 2
4 3
5 3

输出 1

15
12
90

说明

第二个样例测试数据中的 $12$ 个子环图如下图所示。