// Subtasks:
// _: AC
// 4: TLE
// 6: TLE

#include <iostream>
#include <map>
#include <array>
#include <vector>

using namespace std;

#define M 1000000007

int n, m, k;
vector<int> graph[200001];
int deg[200001];
int rem[200001];
vector<vector<int>> graph2[200001];
int m2;

map<array<int,3>,int> dp;

int calc(int node, int prev, int len) {
    if (len > k) return 0;
    if (len == k) {
        return node == n ? 1 : 0;
    }
    array<int,3> key = {node, prev, len};
    if (dp.count(key)) return dp[key];
    long res = 0;
    for (auto next : graph2[node]) {
        if (next[2] != prev) {
            res += calc(next[0], next[2], len+next[1]);
            res %= M;
        }
    }
    dp[key] = res;
    return res;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        deg[a]++;
        deg[b]++;
    }
    vector<int> leaves;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) leaves.push_back(i);
    }
    for (int i = 0; i < leaves.size(); i++) {
        if (leaves[i] != 1 && leaves[i] != n) {
            rem[leaves[i]] = 1;
            for (auto node : graph[leaves[i]]) {
                deg[node]--;
                if (deg[node] == 1) leaves.push_back(node);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (rem[i]) continue;
        if (deg[i] == 2 && i != 1 && i != n) continue;
        for (auto node : graph[i]) {
            int prev = i;
            int steps = 1;
            while (deg[node] == 2 && node != 1 && node != n) {
                steps++;
                for (auto next : graph[node]) {
                    if (rem[next] || next == prev) continue;
                    prev = node;
                    node = next;
                    break;
                }
            }
            if (i <= node) {
                m2++;
                graph2[i].push_back({node, steps, m2});
                if (i != node) {
                    graph2[node].push_back({i, steps, m2});
                }
            }
        }
    }

    cout << calc(1, 0, 0) << "\n";
}
