#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

inline int add(int a, int b) {
	return (a + b >= MOD) ? a + b - MOD : a + b;
}
inline int sub(int a, int b) {
	return (a - b < 0) ? a - b + MOD : a - b;
}
inline int mul(int a, int b) {
	return (long long) a * b % MOD;
}

typedef vector<int> vi;
typedef vector<vi> mat;

mat I(int n) {
	mat C(n, vi(n));
	for(int i = 0;i < n;i++) C[i][i] = 1;
	return C;
}

mat NULA(int n, int m) {
	return mat(n, vi(m));
}

mat mul(mat A, mat B) {
	assert((int)A.size() > 0);
	assert((int)A[0].size() == (int)B.size());
	mat C((int)A.size(), vi((int)B[0].size()));
	for(int i = 0;i < (int)A.size();i++) {
		for(int j = 0;j < (int)B[0].size();j++) {
			for(int k = 0;k < (int)B.size();k++) {
				C[i][j] = add(C[i][j], mul(A[i][k], B[k][j]));
			}
		}
	}
	return C;
}

mat pot(mat A, int B) {
	mat ret = I((int)A.size());
	for(; B ; B >>= 1) {
		if(B&1) ret = mul(ret, A);
		A = mul(A, A);
	}
	return ret;
}

mat S;
int n, m, k;

int main() {
	scanf("%d%d%d", &n, &m, &k);
	vi D(n);
	S = NULA(n, n);
	for(int i = 0;i < m;i++) {
		int a, b; scanf("%d%d", &a, &b); a--; b--;
		S[a][b]++; S[b][a]++;
		D[a]++; D[b]++;
	}
	if(k == 1) {
		printf("%d\n", S[0][n - 1]);
		return 0;
	}
	mat A = NULA(2 * n, 2 * n);
	mat P = NULA(2 * n, n);
	mat SS = mul(S, S);
	for(int i = 0;i < n;i++) {
		A[i][n + i] = 1;
		A[n + i][i] = sub(1, D[i]);
		for(int j = 0;j < n;j++) {
			A[n + i][n + j] = S[i][j];
			P[i][j] = S[i][j];
			P[n + i][j] = sub(SS[i][j], (i == j ? D[i] : 0));
		}
	}
	mat K = mul(pot(A, k - 2), P);
	printf("%d\n", K[n][n - 1]);
	return 0;
}