#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

template <class T> constexpr T power(T a, i64 n) {
    T res{1};
    for (; n > 0; n /= 2, a *= a) {
        if (n % 2 == 1) {
            res *= a;
        }
    }
    return res;
}

template <i64 P> constexpr i64 mul(i64 a, i64 b) {
    i64 res = a * b - i64(1.0L * a * b / P - 0.5L) * P;
    return res % P;
}

template <i64 P> struct ModInt {
    static i64 M;
    constexpr static void setMod(i64 m) { ModInt::M = m; }
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return M;
        }
    }
    i64 x;
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        } else if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr ModInt() : x{} {}
    constexpr ModInt(i64 x) : x{norm(x % getMod())} {}
    constexpr i64 val() const { return x; }
    explicit constexpr operator i64() const { return x; }
    constexpr ModInt operator-() const { return ModInt(getMod() - x); }
    constexpr ModInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr ModInt &operator+=(const ModInt &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt &rhs) {
        if (getMod() < (1LL << 31)) {
            x = 1LL * x * rhs.x % P;
        } else {
            x = mul<getMod()>(x, rhs.x);
        }
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt &rhs) { return *this *= rhs.inv(); }
    friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) { return lhs += rhs; }
    friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) { return lhs -= rhs; }
    friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) { return lhs *= rhs; }
    friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) { return lhs /= rhs; }
    friend constexpr bool operator<(const ModInt &lhs, const ModInt &rhs) { return lhs.val() < rhs.val(); }
    friend constexpr bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(const ModInt &lhs, const ModInt &rhs) { return lhs.val() != rhs.val(); }
    friend istream &operator>>(istream &is, ModInt &rhs) {
        i64 x;
        is >> x;
        rhs = x;
        return is;
    }
    friend ostream &operator<<(ostream &os, const ModInt &rhs) { return os << rhs.val(); }
};

template <i64 V, i64 P> constexpr ModInt<P> CInv = ModInt<P>(V).inv();
template <> i64 ModInt<0>::M = 1000000007;

constexpr int P = 998244353;
using Z = ModInt<P>;

template <class T, const int N> struct Matrix : array<array<T, N>, N> {
    using Base = array<array<T, N>, N>;
    constexpr Matrix(T x = T()) { eye(x); }
    constexpr Matrix(const Base &data) : Base(data) {}
    constexpr void clear() {
        for (int i = 0; i < N; i++) {
            (*this)[i].fill({});
        }
    }
    constexpr void eye(T x) {
        clear();
        for (int i = 0; i < N; i++) {
            (*this)[i][i] = x;
        }
    }
    constexpr Matrix &operator+=(const Matrix &rhs) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                (*this)[i][j] += rhs[i][j];
            }
        }
        return *this;
    }
    constexpr Matrix &operator*=(const Matrix &rhs) {
        Matrix res;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    res[i][j] += (*this)[i][k] * rhs[k][j];
                }
            }
        }
        return *this = move(res);
    }
    friend constexpr Matrix operator+(Matrix lhs, const Matrix &rhs) { return lhs += rhs; }
    friend constexpr Matrix operator*(Matrix lhs, const Matrix &rhs) { return lhs *= rhs; }
    friend constexpr ostream &operator<<(ostream &os, const Matrix &rhs) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                os << rhs[i][j] << " \n"[j == N - 1];
            }
        }
        return os;
    }
};

using Mat = Matrix<Z, 200>;

void solve() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<int> deg(N);
    vector g(N, vector(N, 0));
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u][v] = g[v][u] = 1;
        deg[u]++;
        deg[v]++;
    }

    Mat F;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            F[i][j] = g[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        F[i][N + i] = 1 - deg[i];
        F[N + i][i] = 1;
    }
    F = power(F, K - 2);

    Mat G;
    for (int i = 0; i < N; i++) {
        if (g[0][i]) {
            G[N + i][0] = 1;
            for (int j = 1; j < N; j++) {
                if (g[i][j]) {
                    G[j][0] += 1;
                }
            }
        }
    }

    if (K == 1) {
        cout << G[2 * N - 1][0] << "\n";
    } else {
        cout << (F * G)[N - 1][0] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;

    while (t--) {
        solve();
    }

    return 0;
}