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

#include <iostream>
#include <vector>

using namespace std;

const long M = 1e9+7;

const int N = 200001;
vector<int> adj[N];

int n;

int h(int i, int k, int p=-1) {
    if (k == 0) return i == n;
    int res = 0;
    for (int j : adj[i]) {
        if (j == p) continue;
        res += h(j, k-1, i);
        res %= M;
    }
    return res;
}

int main(int argc, char **argv) {
    int m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cout << h(1, k) << endl;
}
