#include <bits/stdc++.h>
#define ll long long
#define log(x) (63^__builtin_clzll(x))
#define pii pair<ll,ll>
using namespace std;
int n;
const int p=998244353;
namespace Matrix{
	using M=vector<vector<int>>;
	#define M(x,y) M(x,vector<int>(y))
	M operator*(M a,M b){
		M s=M(n<<1,n<<1);
		for(int i=0;i<n*2;i++){
			for(int j=0;j<n*2;j++){
				for(int k=0;k<n*2;k++){
					s[i][j]=(s[i][j]+1ll*a[i][k]*b[k][j])%p;
				}
			}
		}
		return s;
	}
}
using namespace Matrix;
M qpow(M x,ll y){
	M s=M(n<<1,n<<1);
	for(int i=0;i<n*2;i++)s[i][i]=1;
	while(y){
		if(y&1)s=s*x;
		x=x*x;
		y>>=1;
	}
	return s;
}
void solve(){
	int m,k;
	cin>>n>>m>>k;
	M a,b,c;
	a=b=c=M(n<<1,n<<1);
	for(int i=0;i<n;i++){
		b[i+n][i]=b[i][i+n]=1;
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		u--,v--;
		a[u][v]++;a[v][u]++;
		b[n+u][n+v]++;
		b[n+v][n+u]++;

		b[u][n+u]--;
		b[v][n+v]--;
	}
	for(int i=0;i<n*2;i++){
		for(int j=0;j<n*2;j++){
			b[i][j]=(b[i][j]+p)%p;
		}
	}
	c=a*a;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j)continue;
			a[i][n+j]=c[i][j];
		}
	}
	M s=a*qpow(b,k-1);
	cout<<(s[0][n-1])<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	// cin>>t;
	while(t--)solve();
	return 0;
}
/*

*/