// Subtasks:
// 1: AC
// 3: AC
// _: TLE

#include <iostream>
#include <vector>

using namespace std;

#define M 1000000007

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

long total;

void search(int node, int prev, int len) {
    if (len == k) {
        if (node == n) total++;
        return;
    }
    for (auto next : graph[node]) {
        if (next != prev && !rem[next]) {
            search(next, node, len+1);
        }
    }
}

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) {
        erase_if(graph[i], [](int j) {return rem[j];});
    }

    search(1, 0, 0);
    cout << total % M << "\n";
}
