{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eGiven 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 \"sub-cycle\" graph if it\u0027s possible to add a non-negative number of edges to it and turn the graph into exactly one simple cycle of $n$ vertices.\u003c/p\u003e\n\n\u003cp\u003eGiven 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 $10^9+7$.\u003c/p\u003e\n\n\u003cp\u003eRecall that\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eA simple graph is a graph with no self loops or multiple edges;\u003c/li\u003e\n \u003cli\u003eA simple cycle of $n$ ($n \\ge 3$) vertices is a connected undirected simple graph with $n$ vertices and $n$ edges, where the degree of each vertex equals to 2;\u003c/li\u003e\n \u003cli\u003eTwo undirected simple graphs with $n$ vertices and $m$ edges are different, if they have different sets of edges;\u003c/li\u003e\n \u003cli\u003eLet $u$ \u0026lt; $v$, we denote $(u, v)$ as an undirected edge connecting vertices $u$ and $v$. Two undirected edges $(u_1, v_1)$ and $(u_2, v_2)$ are different, if $u_1 \\ne u_2$ or $v_1 \\ne v_2$.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere 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:\u003c/p\u003e\n\n\u003cp\u003eThe first and only line contains two integers $n$ and $m$ ($3 \\le n \\le 10^5$, $0 \\le m \\le \\frac{n(n-1)}{2}$), indicating the number of vertices and the number of edges in the graph.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ in all test cases will not exceed $3 \\times 10^7$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the number of different sub-cycle graphs with $n$ vertices and $m$ edges modulo $10^9+7$.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4 2\n4 3\n5 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\n12\n90\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eThe 12 sub-cycle graphs of the second sample test case are illustrated below.\u003c/p\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/7032cc6768135ea61c4e42a8f1828946?v\u003d1714595903\" width\u003d\"700px\"\u003e\n"}}]}