// Subtasks:
// 3: AC
// _: WA

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const long M = 1e9+7;

int main(int argc, char **argv) {
    int n, m, k;
    cin >> n >> m >> k;
    // was originally set, that is even more buggy
    vector<multiset<pair<int, int>>> g(n+1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].insert({v, 1});
        g[v].insert({u, 1});
    }

    vector<int> z(n+1);
    vector<int> q;
    for (int i = 2; i < n; ++i) if (g[i].size() <= 2) q.push_back(i), z[i] = 1;
    for (int qi = 0; qi < (int)q.size(); ++qi) {
        int i = q[qi];
        if (g[i].size() == 1) {
            auto [j, w] = *g[i].begin();
            g[j].erase({i, w});
            if (j != 1 && j != n && !z[j] && g[j].size() <= 2) q.push_back(j), z[j] = 1;
        } else if (g[i].size() == 2) {
            auto [a, wa] = *g[i].begin();
            auto [b, wb] = *next(g[i].begin());
            int wt = wa + wb;
            g[a].erase({i, wa});
            g[b].erase({i, wb});
            g[a].insert({b, wt});
            g[b].insert({a, wt});
        }
    }

    int nn = 0;
    vector<int> h, hi(n+1);
    for (int i = 1; i <= n; ++i) {
        if (!z[i]) {
            hi[i] = nn;
            h.push_back(i);
            nn++;
        }
    }

    vector<vector<vector<long>>> dp(k+1, vector(nn, vector<long>(nn)));
    dp[0][0][0] = 1;
    for (int d = 0; d < k; ++d) {
        for (int pr = 0; pr < nn; ++pr) {
            for (int i = 0; i < nn; ++i) {
                for (auto [j, w] : g[h[i]]) {
                    j = hi[j];
                    if (d + w > k || j == pr) continue;
                    dp[d + w][i][j] += dp[d][pr][i];
                    dp[d + w][i][j] %= M;
                }
            }
        }
    }

    long res = 0;
    for (int pr = 0; pr < nn; ++pr) res = (res + dp[k][pr][nn-1]) % M;
    cout << res << endl;
}
