#include using namespace std; const int MOD = 998244353; int N, M; long long T; vector> mul(const vector> &A, const vector> &B) { vector> ret(2*N, vector(2*N, 0)); for (int i = 0; i < 2*N; i++) { for (int j = 0; j < 2*N; j++) { for (int k = 0; k < 2*N; k++) { ret[i][j] += A[i][k] * B[k][j] % MOD; ret[i][j] %= MOD; } } } return ret; } vector> mulx(const vector> &A, const vector> &B) { vector> ret(2*N, vector(N, 0)); for (int i = 0; i < 2*N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < 2*N; k++) { ret[i][j] += A[i][k] * B[k][j] % MOD; ret[i][j] %= MOD; } } } return ret; } int main() { cin >> N >> M >> T; vector> edge(N, vector(N, 0)); for (int i = 0; i < M; i++) { int s, t; cin >> s >> t; edge[s][t] = edge[t][s] = 1; } vector> mat(2*N, vector(2*N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { mat[i][j] = mat[i+N][j] = edge[i][j]; } mat[i+N][i+N] = 1; } vector> A(2*N, vector(2*N, 0)); for (int i = 0; i < 2*N; i++) A[i][i] = 1; T--; while (T > 0) { if (T & 1) { A = mul(A, mat); } mat = mul(mat, mat); T /= 2; } vector> B(2*N, vector(N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { B[i][j] = edge[i][j]; } B[i+N][i] = 1; } B = mulx(A, B); cout << B[0][0] << endl; }