Read problems statements in mandarin chinese, russian and vietnamese as well.

You are given an undirected graph G = (V, E). We define a function f(s) for s ⊆ V to be the number of edges in the induced subgraph of s.

The problem asks you to calculate the sum of f(s)^{k} over all s in 2^{|V|} subsets of V.

As the answer could be very large, output it modulo (10^{9}+7).

------ Input ------

The first line of input contains an integer T denoting the number of test cases.
For each test case, the first line contains three space-separated integers n = |V|, m = |E| and k.
Then m lines follow, each line contains two space-separated integers u, v denoting an edge (u, v) is in E.

------ Output ------

For each test case, output one line containing one integer, the answer modulo (10^{9}+7).

------ Constraints ------

    1 ≤ T ≤ 100

    2 ≤ n ≤ 10^{5}

    0 ≤ m ≤ 10^{5}
Sum of each of n, m over all test cases ≤ 3 * 10^{5}
1 ≤ u, v ≤ n.

    1 ≤ k ≤ 3.
The graph is simple, i.e., doesn't contain self loops and multiple edges.

------ Subtasks ------

Subtask #1 (8 points): T, n ≤ 15
Subtask #2 (7 points): k = 1
Subtask #3 (9 points): k = 2
Subtask #4 (15 points):

    k = 3.
    Sum of n over all test cases ≤ 300
    Sum of m over all test cases ≤ 300

Subtask #5 (24 points):

    k = 3.
    Sum of n over all test cases ≤ 3000
    Sum of m over all test cases ≤ 3000

Subtask #6 (37 points): Original Constraints

----- Sample Input 1 ------
3

3 3 1

1 2

2 3

3 1

4 5 2

1 2

2 3

3 4

4 1

2 4

5 4 3

1 2

1 3

1 4

2 5
----- Sample Output 1 ------
6

56

194
----- explanation 1 ------
Example case 1.
f(emptyset) = f({1}) = f({2}) = f({3}) = 0;
f({1, 2}) = f({2, 3}) = f({3, 1}) = 1
f({1, 2, 3}) = 3.
So the answer is 1 + 1 + 1 + 3 = 6.

Example case 2.
The nonzero f's are as follows
f({1, 2}) = f({2, 3}) = f({3, 4}) = f({4, 1}) = f({2, 4}) = 1
f({1, 2, 3}) = f({1, 3, 4}) = 2
f({1, 2, 4}) = f({2, 3, 4}) = 3
f({1, 2, 3, 4}) = 5

So the answer is 5 * 12 + 2 * 22 + 2 * 32 + 52 = 56.

见题面

见题面