Counting Subgraphs

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Kostya recently began his internship in a very big and famous IT company. His first project is dedicated to visualization of graphs, but his manager wanted to make sure Kostya is good enough for this project before he starts writing any code. As it usually goes, Kostya was given an algorithmic problem and was asked to come up with a solution. After struggling with the problem for a couple of days, he finally managed to solve it. Now Kostya wants to challenge the participants of the September CookOff 2015 Contest with this problem. Unfortunately, you don't have a couple of days to solve it, and you'll have to make do with 2.5 hours. Are you ready to be challenged? :)
You are given an undirected graph G of N nodes and M edges. The nodes of G are labeled with unique integer numbers of the range [1, 2, ... , N]. It's guaranteed that no multiple edges or selfloops appear in the graph as well as that the graph is connected. There's one more restriction on the graph: any node of G belongs to at most one simple cycle in G.
Your task is to count the subsets of nodes in G, such that the nodes in the subset are connected (you can reach any node of the subset from any other node of the subset only by moving to adjacent nodes that belong to the subset) and contain no more than K nodes. Since the answer may exceed the limits of usual primitive integer types, you are asked to do all the calculations modulo 10^{9} + 7.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of a test case description contains three integers N, M and K.
Each of the next M lines contains two integers U and V denoting a single edge in G between the vertices labeled U and V.
Output
For each test case, output a single line containing one integer: the number of described subsets modulo 10^{9} + 7.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 5000
 0 ≤ M ≤ 10000
 1 ≤ K ≤ min(N, 30)
 1 ≤ U ≠ V ≤ N
 The size of any simple cycle in G does not exceed L = 50
Example
Input: 3 3 2 1 2 1 3 1 5 5 4 5 4 4 3 1 5 3 2 2 5 3 2 2 2 3 1 3 Output: 3 20 5
Author:  kostya_by 
Tester:  shangjingbo 
Editorial  http://discuss.codechef.com/problems/SUBGRAPH 
Tags  cook62, dynamicprogramming, graph, kostya_by, mediumhard, tree 
Date Added:  25072015 
Time Limit:  10 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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