SP11813 CNTPATHS - Count weighted paths

John likes to take a walk from his house to university. He needs to arrive his university in at most **T** seconds after leaving his home. We can represent the situation as a **N** vertices graph. Vertex 0 of the graph will be John's home and vertex 1 John's university. There can be bidirectional roads connecting pairs of vertices, each road will take John some seconds to cross. John likes variety. We consider a valid path to be a sequence of vertices that starts with vertex 0 (John's house) and finishes with vertex 1 (The University) and there exists a road connecting each pair of consecutive vertices in the sequences (Note that a vertex may appear multiple times in the path). The total time John needs to traverse a path is equal to the sum of the times needed to cross each individual road in it. Please count the total number of different paths that need at most **T** minutes to be traversed in total. Two paths are different if there is at least one moment at which they visit different vertices. Given **T**, **N** and the roads between the vertices, ¿How many different paths that need at most **T** seconds exist? Print the result modulo 1000000007 (10 $ ^{9} $ +7).

The first line consists of a integer **TOTAL**, the total number of test cases (1

For each test case, show in a single line: "Case #i: R", where R is the total number of valid paths between vertices 0 and 1 donde R that need a quantity of at most **T** segundos .