// Subtasks:
// 1: AC
// 2: AC
// 5: AC
// _: TLE

#include <iostream>

#define ll long long
#define M 1000000007
#define N (1<<18)

using namespace std;

pair<int, int> e[2 * N];
ll am[2 * N];
ll nam[2 * N];
ll sum[N];

int main() {
    int n, m, k;
    cin>>n>>m>>k;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin>>x>>y;
        e[2 * i] = {x, y};
        e[2 * i + 1] = {y, x};
    }
    sum[1] = 1;
    while (k --> 0) {
        for (int i = 0; i < 2 * m; i++) {
            sum[e[i].second] += am[i];
        }
        for (int i = 0; i < 2 * m; i += 2) {
            nam[i] += sum[e[i].first] - am[i + 1];
            nam[i + 1] += sum[e[i + 1].first] - am[i];
        }
        for (int i = 0; i < 2 * m; i++) {
            am[i] = nam[i] % M;
            nam[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            sum[i] = 0;
        }
    }
    for (int i = 0; i < 2 * m; i++) {
        sum[e[i].second] += am[i];
        sum[e[i].second] %= M;
    }
    cout<<sum[n]<<endl;
}
