L. Sub-cycle Graph
time limit per test
2.0 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Given an undirected simple graph with n (n ≥ 3) vertices and m edges where the vertices are numbered from 1 to n, we call it a "sub-cycle" graph if it's possible to add a non-negative number of edges to it and turn the graph into exactly one simple cycle of n vertices.

Given two integers n and m, your task is to calculate the number of different sub-cycle graphs with n vertices and m edges. As the answer may be quite large, please output the answer modulo 109 + 7.

Recall that

  • A simple graph is a graph with no self loops or multiple edges;
  • A simple cycle of n (n ≥ 3) vertices is a connected undirected simple graph with n vertices and n edges, where the degree of each vertex equals to 2;
  • Two undirected simple graphs with n vertices and m edges are different, if they have different sets of edges;
  • Let u < v, we denote (u, v) as an undirected edge connecting vertices u and v. Two undirected edges (u1, v1) and (u2, v2) are different, if u1 ≠ u2 or v1 ≠ v2.
Input

There are multiple test cases. The first line of the input contains an integer T (about 2 × 104), indicating the number of test cases. For each test case:

The first and only line contains two integers n and m (3 ≤ n ≤ 105, ), indicating the number of vertices and the number of edges in the graph.

It's guaranteed that the sum of n in all test cases will not exceed 3 × 107.

Output

For each test case output one line containing one integer, indicating the number of different sub-cycle graphs with n vertices and m edges modulo 109 + 7.

Example
Input
3
4 2
4 3
5 3
Output
15
12
90
Note

The 12 sub-cycle graphs of the second sample test case are illustrated below.