Unlike Dystopia, the neighbouring nation of Utopia believes in economic development. To improve the economy of the nation, the Utopian government has decided to select some pairs of cities as sister cities and take steps to improve trade relations between each pair.

There are N cities in Utopia, numbered 1 to N. There are two-way roads connecting some pairs of cities. The total number of roads in Utopia is R. Now the road network in Utopia has been created efficiently so that there is no road that is redundant. That is, there is exactly one way to travel between any pair of cities without using the same road twice. Now when a pair of cities is chosen as sister cities, the government wants to make sure that there is a direct road between them. Also, a given city cannot have more than one sister.

Given the road network of Utopia, find the number of ways of selecting K pairs of sister cities under these constraints. As the answer can be quite large, output it modulo 100000007.

For example, assume that there are 6 cities in Utopia. There are direct roads between the following pairs of cities : (1,2), (2,3), (2,4), (4,5), (4,6). Notice that there is exactly one way to travel between any pair of cities. If the government wants to select two pairs of sister cities, it can do it in four ways : {(1,2),(4,5)}, {(3,2),(4,5)}, {(1,2),(4,6)}, {(3,2),(4,6)}

Input

First line of the input contains T (≤10), the number of test cases. This is followed by the description of the test cases.

The description of each test case begins with a line containing 3 space separated integers N (<400), R (<10000) and K (<400). Following these are R lines, each representing a road in Utopia. The line will contain two different space separated integers N₁ and N₂ implying that there is a two way road between N₁ and N₂. You are assured that the road network has the property as described in the problem statement.

Output

For each test case, output modulo 100000007 the number of ways of selecting K pairs of sister cities satisfying the conditions in the problem statement.

Example

Input:
2
3 2 1
1 2
2 3
6 5 2
1 2
2 3
2 4
4 5
4 6
Output:
2
4