#pragma GCC target("avx") #pragma GCC optimize("O2") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; int N, M; long long T; vector<vector<long long>> mul(const vector<vector<long long>> &A, const vector<vector<long long>> &B) { vector<vector<long long>> ret(N, vector<long long>(N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { ret[i][j] += A[i][k] * B[k][j]; ret[i][j] %= MOD; } } } return ret; } int main() { cin >> N >> M >> T; vector<vector<long long>> mat(N, vector<long long>(N, 0)); for (int i = 0; i < M; i++) { int s, t; cin >> s >> t; mat[s][t] = mat[t][s] = 1; } vector<vector<long long>> A(N, vector<long long>(N, 0)); for (int i = 0; i < N; i++) A[i][i] = 1; while (T > 0) { if (T & 1) { A = mul(A, mat); } mat = mul(mat, mat); T >>= 1; } cout << A[0][0] << endl; }