{"raw_statement":[{"iden":"problem statement","content":"You are given a simple connected undirected graph $G$ consisting of $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $M$.\nEdge $i$ connects Vertex $a_i$ and $b_i$ bidirectionally. It is guaranteed that the subgraph consisting of Vertex $1,2,\\ldots,N$ and Edge $1,2,\\ldots,N-1$ is a spanning tree of $G$.\nAn allocation of weights to the edges is called a _good allocation_ when the tree consisting of Vertex $1,2,\\ldots,N$ and Edge $1,2,\\ldots,N-1$ is a minimum spanning tree of $G$.\nThere are $M!$ ways to allocate the edges distinct integer weights between $1$ and $M$. For each good allocation among those, find the total weight of the edges in the minimum spanning tree, and print the sum of those total weights modulo $10^{9}+7$."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2 \\leq N \\leq 20$\n*   $N-1 \\leq M \\leq N(N-1)/2$\n*   $1 \\leq a_i, b_i \\leq N$\n*   $G$ does not have self-loops or multiple edges.\n*   The subgraph consisting of Vertex $1,2,\\ldots,N$ and Edge $1,2,\\ldots,N-1$ is a spanning tree of $G$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$\\vdots$\n$a_M$ $b_M$"},{"iden":"sample input 1","content":"3 3\n1 2\n2 3\n1 3"},{"iden":"sample output 1","content":"6\n\nAn allocation is good only if Edge $3$ has the weight $3$. For these good allocations, the total weight of the edges in the minimum spanning tree is $3$, and there are two good allocations, so the answer is $6$."},{"iden":"sample input 2","content":"4 4\n1 2\n3 2\n3 4\n1 3"},{"iden":"sample output 2","content":"50"},{"iden":"sample input 3","content":"15 28\n10 7\n5 9\n2 13\n2 14\n6 1\n5 12\n2 10\n3 9\n10 15\n11 12\n12 6\n2 12\n12 8\n4 10\n15 3\n13 14\n1 15\n15 12\n4 14\n1 7\n5 11\n7 13\n9 10\n2 7\n1 9\n5 6\n12 14\n5 2"},{"iden":"sample output 3","content":"657573092\n\nPrint the sum of those total weights modulo $10^{9}+7$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}