#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

constexpr i64 MOD = 998244353;
constexpr int L = 300;
using Mat = array<array<int, L>, L>;

Mat matMul(Mat a, Mat b) {
    Mat res{};
    for (int i = 0; i < L; i++) {
        for (int k = 0; k < L; k++) {
            for (int j = 0; j < L; j++) {
                res[i][j] += i64(a[i][k]) * b[k][j] % MOD;
                if (res[i][j] >= MOD) res[i][j] -= MOD;
            }
        }
    }
    return res;
}

void debug(Mat a, int n) {
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) {
            cout << a[i][j];
            if (j != 2 * n - 1) cout << ", ";
        }
        cout << ";\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k; cin >> n >> m >> k;
    Mat trans{};
    Mat w0{};
    vector<int> deg(n);
    while (m--) {
        int u, v; cin >> u >> v;
        u--, v--;
        trans[u][v]++;
        trans[v][u]++;
        deg[u]++, deg[v]++;
    }
    for (int u = 0; u < n; u++) {
        trans[u + n][u] = (MOD - deg[u]) % MOD;
        trans[u][n + u] = 1;
        trans[u + n][u + n + n] = 1;
        trans[u + n + n][u + n] = 1;
        w0[u][u] = 1;
    }
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            trans[u + n + n][v] = trans[u][v];
        }
    }
    // debug(w0, n);
    // debug(trans, n);
    // debug(matMul(w0, trans), n);
    // debug(matMul(w0, matMul(trans, trans)), n);
    while (k) {
        if (k & 1) w0 = matMul(w0, trans);
        trans = matMul(trans, trans);
        k >>= 1;
    }
    cout << w0[0][n - 1] << endl;
}