
ZOJ Problem Set  4069
Given an undirected simple graph with $n$ ($n \ge 3$) vertices and $m$ edges where the vertices are numbered from 1 to $n$, we call it a "subcycle" graph if it's possible to add a nonnegative 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 subcycle graphs with $n$ vertices and $m$ edges. As the answer may be quite large, please output the answer modulo $10^9+7$. Recall that
InputThere are multiple test cases. The first line of the input contains an integer $T$ (about $2 \times 10^4$), indicating the number of test cases. For each test case: The first and only line contains two integers $n$ and $m$ ($3 \le n \le 10^5$, $0 \le m \le \frac{n(n1)}{2}$), 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 \times 10^7$. OutputFor each test case output one line containing one integer, indicating the number of different subcycle graphs with $n$ vertices and $m$ edges modulo $10^9+7$. Sample Input3 4 2 4 3 5 3 Sample Output15 12 90 HintThe 12 subcycle graphs of the second sample test case are illustrated below. Author: WENG, Caizhi Source: The 2018 ACMICPC Asia Qingdao Regional Contest 