#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef unsigned long long u64;
typedef double lf;

const int mod = 998244353;
template<typename T>
T add(T x) {
    return x;
}
template<typename T, typename... Ts>
T add(T x, Ts... y) {
    T res = x + add(y...);
    if (res >= mod)
        res -= mod;
    return res;
}
template<typename T, typename... Ts>
T sub(T x, Ts... y) {
    return add(x, mod - add(y...));
}
template<typename T, typename... Ts>
void udd(T &x, Ts... y) {
    x = add(x, y...);
}
template<typename T>
T mul(T x) {
    return x;
}
template<typename T, typename... Ts>
T mul(T x, Ts... y) {
    return (x * 1ll * mul(y...)) % mod;
}
template<typename T, typename... Ts>
void uul(T &x, Ts... y) {
    x = mul(x, y...);
}
typedef vector<vector<int>> matrix;

vector<int> poly_mul(const vector<int> &a, const vector<int> &b, const vector<int> &f) {
    vector<int> ret(a.size() + b.size() - 1);
    // ret = a * b
    for (size_t i = 0; i < a.size(); i++) {
        for (size_t j = 0; j < b.size(); j++) {
          udd(ret[i + j], mul(a[i], b[j]));
        }
    }
    // reducing ret mod f(x)
    int n = (int) f.size();
    for (int i = (int) ret.size()-1; i >= n; i--) {
        for (int j = n - 1; j >= 0; j--) {
          udd(ret[i - j - 1], mul(ret[i], f[j]));
        }
    }
    ret.resize(min((int) ret.size(), n));
    return ret;
}
 
int rec_eval(const vector<int> &c, const vector<int> &s, long long k) {
    int n = (int) c.size();
    assert(c.size() <= s.size());
 
    vector<int> a = (n == 1) ? vector<int>{c[0]} : vector<int>{0, 1};
    vector<int> x{1};
    for (; k > 0; k /= 2) {
        if (k % 2)
            x = poly_mul(x, a, c);
        a = poly_mul(a, a, c);
    }
    x.resize(n);
 
    int ret = 0;
    for (int i = 0; i < n; i++) {
      udd(ret, mul(x[i], s[i]));
    }
    return ret;
}

namespace BerlekampMassey {
    int L, m, b, n;
    vector<int> s, C, B;
    void init() {
        s.clear();
        C.clear();
        B.clear();
        C.push_back(1);
        B.push_back(1);
        L = n = 0;
        m = b = 1;
    }
    int pow_mod(int a, int k) {
        int s = 1;
        while (k) {
            if (k & 1)
                s = 1ll * s * a % mod;
            a = 1ll * a * a % mod;
            k >>= 1;
        }
        return s;
    }
    void update(int d) {
		s.push_back(d);
		for (int i = 1; i <= L; ++i)
			d = (d + 1ll * C[i] * s[n - i] % mod) % mod;
		if (d == 0)
			++m;
		else if (2 * L <= n) {
			vector<int> T = C;
			C.resize(n + 1 - L + 1);
			for (int i = L + 1; i <= n + 1 - L; ++i)
				C[i] = 0;
			for (int i = 0; i < B.size(); ++i)
				C[i + m] = (C[i + m] + mod - 1ll * d * pow_mod(b, mod - 2) % mod * B[i] % mod) % mod;
			L = n + 1 - L;
			B = T;
			b = d;
			m = 1;
		} else {
			for (int i = 0; i < B.size(); ++i)
				C[i + m] = (C[i + m] + mod - 1ll * d * pow_mod(b, mod - 2) % mod * B[i] % mod) % mod;
			++m;
		}
		++n;
    }
    
    vector<int> get_min_rec() {
        vector<int> ret;
        for (int i = 1; i < C.size(); ++i) {
			int output = (mod - C[i]) % mod;
            ret.push_back(output);
            // cerr << output << ",";
		}
        return ret;
    }
};


void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    matrix a(n, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        a[u][v]++;
        a[v][u]++;
    }
    if (n == 1) {
        cout << 0 << '\n';
        return;
    }
    vector<int> v(n * n);
    vector<int> nv(n * n);
    v[0] = 1;

    BerlekampMassey::init();
    int need = 3 * n * n + 10;

    vector<int> answers;
    answers.push_back(0);
    BerlekampMassey::update(0);
    for (int it = 0; it < need; ++it) {
        fill(nv.begin(), nv.end(), 0);
        for (int c = 0; c < n * n; ++c) {
            if (v[c] == 0) {
                continue;
            }
            int prev = c % n;
            int cur = c / n;
            for (int to = 0; to < n; to++) {
                if (to != prev && a[cur][to]) {
                    udd(nv[to * n + cur], v[c]);
                }
            }
        }
        v.swap(nv);

        int ans = 0;
        for (int i = 0; i + 1 < n; ++i) {
            udd(ans, v[(n - 1) * n + i]);
        }
        BerlekampMassey::update(ans);
        answers.push_back(ans);
    }
    auto coeffs = BerlekampMassey::get_min_rec();
    // cerr << coeffs.size() << endl;
    cout << rec_eval(coeffs, answers, k) << '\n';
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
}