/*
The key condition is that every node belongs to at most ONE simple cycle. Besides, the input graph is connected.

Assume we are doing DFS on the graph, as it is an undirected graph, there are only several back-edges except for the tree-edges. Moreover, there will be no intersections between back-edges (since the simple cycles have no intersections).

Therefore, we can use (node u, total number of selected nodes, # connected components in subtree u, whether u is selected, whether there is a component has a back-edge going beyond node u) to describe the states. # connected components <= 2, others are all binary indicators. Therefore, the total number of states is O(NK). There is another dynamic programming among all children of node u for the transition part. Therefore, the total time complexity is O(NK^2). You can check the details in my submission.
*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;

const int MOD = 1000000007;

void add(int &a, int b)
{
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

const int MAXN = 5000;
const int MAXM = 10000;
const int MAXK = 30;

vector<int> adj[MAXN];
int depth[MAXN], direct_backto[MAXN], subtree_backto[MAXN], subtree_size[MAXN];
int f[MAXN][MAXK + 1][2][2][3][2], tmp[MAXK + 1][2][2][3][2];
int n, m, k;

void tree_dp(int u)
{
    f[u][1][1][direct_backto[u] != -1][1][1] = 1;
    f[u][0][0][0][0][0] = 1;
    int total_nodes = 1;
    for (int i = 0; i < adj[u].size(); ++ i) {
        int v = adj[u][i];
        if (depth[v] == depth[u] + 1) {
            tree_dp(v);
            for (int su = 0; su <= total_nodes && su <= k; ++ su)
            for (int sel_u = 0; sel_u < 2; ++ sel_u)
            for (int go_up_u = 0; go_up_u < 2; ++ go_up_u)
            for (int comp_u = 0; comp_u < 3; ++ comp_u)
            for (int same_u = 0; same_u < 2; ++ same_u) {
                long long t = f[u][su][sel_u][go_up_u][comp_u][same_u];
                if (t == 0) {
                    continue;
                }
                for (int sel_v = 0; sel_v < 2; ++ sel_v)
                for (int go_up_v = 0; go_up_v < 2; ++ go_up_v)
                for (int comp_v = 0; comp_v < 3; ++ comp_v)
                for (int same_v = 0; same_v < 2; ++ same_v) {
                    int comp = comp_u + comp_v;
                    // check connections
                    if (sel_u == 1 && sel_v == 1) {
                        -- comp;
                    } else {
                        if (comp_v == 2) {
                            continue;
                        }
                    }
                    if (same_v == 0 && sel_u == 1 && go_up_v == 1 && subtree_backto[v] == u) {
                        -- comp;
                    }

                    if (comp > 2) {
                        continue;
                    }
                    comp = max(comp, 0);

                    int same = same_u;

                    int go_up = go_up_u;
                    if (go_up_v == 1 && subtree_backto[v] != u) {
                        go_up = 1;
                        same = sel_u == 1 && sel_v == 1 && same_v == 1;
                    }

                    for (int sv = 0; sv <= subtree_size[v] && su + sv <= k; ++ sv) {
                        add(tmp[su + sv][sel_u][go_up][comp][same], t * f[v][sv][sel_v][go_up_v][comp_v][same_v] % MOD);
                    }
                }
            }
            total_nodes += subtree_size[v];
            for (int s = 0; s <= total_nodes && s <= k; ++ s) {
                memcpy(f[u][s], tmp[s], sizeof(tmp[s]));
                memset(tmp[s], 0, sizeof(tmp[s]));
            }
        }
    }
}

int dfs(int u)
{
    int go_up = -1;
    subtree_size[u] = 1;
    for (int i = 0; i < adj[u].size(); ++ i) {
        int v = adj[u][i];
        if (depth[v] == -1) {
            //fprintf(stderr, "%d -> %d\n", u, v);
            depth[v] = depth[u] + 1;
            int go_up_v = dfs(v);
            subtree_size[u] += subtree_size[v];
            if (go_up_v != -1) {
                assert(go_up == -1); // each node belongs to at most ONE simple cycle
                go_up = go_up_v;
            }
        } else if (depth[v] < depth[u] - 1) {
            direct_backto[u] = v;
            assert(go_up == -1);
            assert(depth[u] - depth[v] + 1 <= 50); // simple cycle size
            go_up = v;
        }
    }
    if (go_up == u) {
        go_up = -1;
    }
    //fprintf(stderr, "%d go back to %d\n", u, go_up);
    return subtree_backto[u] = go_up;
}

int main()
{
    int tests;
    for (assert(scanf("%d", &tests) == 1 && 1 <= tests && tests <= 10);tests --;) {
        assert(scanf("%d%d%d", &n, &m, &k) == 3 && 1 <= n && n <= MAXN && 0 <= m && m <= MAXM && 1 <= k && k <= min(n, MAXK));
        for (int i = 0; i < n; ++ i) {
            adj[i].clear();
        }
        for (int i = 0; i < m; ++ i) {
            int a, b;
            assert(scanf("%d%d", &a, &b) == 2);
            assert(1 <= a && a <= n);
            assert(1 <= b && b <= n);
            assert(a != b);
            -- a;
            -- b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        memset(depth, -1, sizeof(depth));
        memset(direct_backto, -1, sizeof(direct_backto));
        memset(subtree_backto, -1, sizeof(subtree_backto));
        depth[0] = 0;
        dfs(0);

        // connected
        for (int i = 0; i < n; ++ i) {
            assert(depth[i] != -1);
        }

        memset(f, 0, sizeof(f));
        memset(tmp, 0, sizeof(tmp));
        tree_dp(0);

        int answer = 0;
        for (int u = 0; u < n; ++ u) {
            for (int s = 1; s <= k; ++ s) {
                for (int go_up = 0; go_up < 2; ++ go_up) {
                    for (int same = 0; same < 2; ++ same) {
                        if (f[u][s][1][go_up][1][same]) {
                            add(answer, f[u][s][1][go_up][1][same]);
                        }
                    }
                }
            }
        }

        printf("%d\n", answer);
    }
    return 0;
}