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

constexpr int P = 998244353;

struct Matrix {
    int n, m;
    vector<vector<int>> a;
    Matrix(int n_ = 0, int m_ = 0) {
        n = n_, m = m_;
        a.resize(n, vector<int>(m, 0));
    }
    vector<int> &operator[](int x) {
        return a[x];
    }
    Matrix neg() {
        Matrix c(n, m);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(a[i][j]) c[i][j] = P - a[i][j];
            }
        }
        return c;
    }
};
Matrix operator*(Matrix a, Matrix b) {
    assert(a.m == b.n);
    Matrix c(a.n, b.m);
    for(int k = 0; k < a.m; k++) {
        for(int i = 0; i < a.n; i++) {
            for(int j = 0; j < b.m; j++) {
                c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j]) % P;
            }
        }
    }
    return c;
}
Matrix operator+(Matrix a, Matrix b) {
    Matrix c(a.n, a.m);
    for(int i = 0; i < a.n; i++) {
        for(int j = 0; j < a.m; j++) {
            c[i][j] = a[i][j] + b[i][j];
            c[i][j] >= P ? c[i][j] -= P : 0;
        }
    }
    return c;
}
Matrix operator-(Matrix a, Matrix b) {
    Matrix c(a.n, a.m);
    for(int i = 0; i < a.n; i++) {
        for(int j = 0; j < a.m; j++) {
            c[i][j] = a[i][j] - b[i][j];
            c[i][j] < 0 ? c[i][j] += P : 0;
        }
    }
    return c;
}
Matrix operator-(Matrix a) {
    Matrix c(a.n, a.m);
    for(int i = 0; i < a.n; i++) {
        for(int j = 0; j < a.m; j++) {
            if(a[i][j]) c[i][j] = P - a[i][j];
        }
    }
    return c;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    Matrix G(n, n), D(n, n), I(n, n);
    for(int i = 0; i < n; i++) I[i][i] = 1;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u][v] = G[v][u] = 1;
        D[u][u]++, D[v][v]++;
    }
    Matrix F0(n, 1);
    F0[0][0] = 1;
    // cerr << "ok\n";
    Matrix F1 = G * F0, F2 = G * F1 - D * F0;
    // cerr << "ok\n";
    if(k == 1) {
        cout << F1[n - 1][0] << '\n';
        return;
    }
    // cerr << "ok\n";
    Matrix DI = I - D;
    Matrix mat(2 * n, 2 * n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            mat[i][j] = G[i][j];
            mat[i][j + n] = DI[i][j];
            mat[i + n][j] = I[i][j];
        }
    }
    auto qpow = [&](Matrix a, int b) {
        Matrix res(a.n, a.m);
        for(int i = 0; i < a.n; i++) res[i][i] = 1;
        while(b) {
            if(b & 1) res = res * a;
            a = a * a, b >>= 1;
        }
        return res;
    };
    mat = qpow(mat, k - 2);
    Matrix F(2 * n, 1);
    for(int i = 0; i < n; i++) {
        F[i][0] = F2[i][0];
        F[i + n][0] = F1[i][0];
    }
    F = mat * F;
    cout << F[n - 1][0] << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}