Future of draughts

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
2367. The Earth.
The world we know doesn't exist anymore. All has been changed during the inevitable evolution, but only Chef retains his former self.
Peoples don’t play ordinary draughts we know, mankind has enhanced it. Present games are held on an undirected graph, instead of the board. Before a game starts, one player chooses a vertex of the graph and puts a checker (called the game checker) on it. Then the players take turns alternately. In a single turn, a player moves the game checker from its current vertex, say v, to some neighbour (see note) of v. The game goes on until one of the players surrenders. The player who moves last is considered as the winner. This game may seems to you confusing. Strange even, and imperfect, but don’t bother about it.
Chef would like to become the best in this game so he needs training. During training, Chef plays by himself. Being very tired, all of his moves are absolutely random as well as his choice for the initial position of the game checker. He has T gamegraphs (indexed 1 to T), and a very tiresome trainer who forces him to train again and again. For the i^{th} training session, the trainer gives 3 numbers to Chef: L_{i}, R_{i}, and K_{i}. Chef has to carry out a few simultaneous games against himself on gamegraphs indexed between L_{i} and R_{i} (both included).
Specifically, after the trainer gives him such an order, for each gamegraph in range L_{i} … R_{i} Chef randomly sets initial position of the game checker. Further, for each of the following steps, he should choose a random nonempty subset of the set of allowed gamegraphs. Then he randomly moves one checker in all of these chosen gamegraphs. The whole training ends after finite number of steps if the set of current positions after last step is the same as the set of initial positions. Note that Chef must make at least one move during this training.
The trainer wants Q training sessions, as described above, and for each one of them Chef would like to know how many ways of his play lead to the whole training ending within K_{i} steps or less. Since the answer could be very large, print it modulo 1000000007.
Input
The first line of the input contains a single integer T denoting the number of graphs. The description of T graphs follows.
The first line of each graph description contains two integers N_{k}, M_{k} denoting the number of vertices and the number of edges in the kth graph. Next M_{k} lines contain two space separated integers  1indexed indices of vertex pairs linked with an edge.
It is guaranteed that there are no multiple edges (two or more edges incident on the same two vertices) or loops (an edge connecting a vertex to itself).
After graph descriptions, a single line contains an integer Q, denoting the number of training sessions. Each of the next Q lines contain three spaceseparated integers, with the i^{th} line containing the integers L_{i}, R_{i}, K_{i}, respectively, describing the i^{th} training session.
Output
For each query, print a single integer  the number Chef would like to find out modulo 1000000007 (10^{9}+7).
Constraints and Subtasks
 1 ≤ T, N_{k} ≤ 50
 0 ≤ M_{k} ≤ N_{k}×(N_{k}−1)/2
 1 ≤ Q ≤ 2×10^{5}
 1 ≤ L_{i} ≤ R_{i} ≤ T
 1 ≤ K_{i} ≤ 10^{4}
Subtask 1: (10 points)
 L_{i} = R_{i}
 1 ≤ K_{i} ≤ 100
 Time Limit is 2 seconds
Subtask 2: (25 points)
 1 ≤ K_{i} ≤ 100
 Time Limit is 2 seconds
Subtask 3: (25 points)
 1 ≤ K_{i} ≤ 2×10^{3}
 1 ≤ N_{k} ≤ 15
 Time Limit is 8 seconds
Subtask 4: (40 points)
 1 ≤ T ≤ 20
 Time Limit is 10 seconds
Example
Input: 1 3 3 1 2 2 3 1 3 3 1 1 1 1 1 3 1 1 4 Output: 0 12 30 Input: 2 3 2 1 2 2 3 2 1 1 2 3 1 1 6 1 2 2 1 2 10 Output: 28 22 915822
Explanation
Example case 1.
Starts from: (ways of play with length in range [1, 4])
1: (1,2,1), (1,3,1), (1,2,3,1), (1,3,2,1), (1,2,3,2,1),
(1,3,2,3,1), (1,2,1,3,1),(1,3,1,2,1),(1,2,1,2,1),(1,3,1,3,1)
2, 3: similar to 1.
So, the number of ways of play with length at most 3 equals 4×3 = 12.
And, the number of ways of play with length at most 4 equals to 10×3 = 30.
Example case 2.
Starts from: (ways of play with length = 2)
(1,1): ((1,1), (2,1), (1,1)), ((1,1), (1,2), (1,1)), ((1,1), (2,2), (1,1))
(2,1): ((2,1), (1,1), (2,1)), ((2,1), (2,2), (2,1)), ((2,1), (3,1),(2,1)),
((2,1), (1,2),(2,1)),((2,1),(3,2),(2,1))
(3,1): similar to (1,1)
So, the according to symmetry of second graph number of ways equals to (3×2+5)×2 = 22.
Note
In an undirected graph, a vertex u is called a neighbour of vertex v, if u and v are connected via an edge.
Author:  kaizer 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/CLOWAY 
Tags  algebra, aug15, fourier, graph, kaizer, linear, spectral, superhard 
Date Added:  12072015 
Time Limit:  2  10 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 