#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205,mod=998244353;
int n,m,k,d[N];
vector<int>e[N];
struct Mat{
	ll a[N][N];
	Mat(int p=0){memset(a,0,sizeof(a));if(p)for(int i=1;i<=n*2;i++)a[i][i]=1;}
	friend Mat operator*(const Mat&x,const Mat&y) {
		Mat z;
		for(int i=1;i<=n*2;i++)for(int j=1;j<=n*2;j++)for(int k=1;k<=n*2;k++)	
			z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
		return z;
	}
};
Mat qp(Mat a,int b){Mat ans(1);for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;return ans;}
int main() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1,x,y;i<=m;i++)cin>>x>>y,e[x].push_back(y),e[y].push_back(x),d[x]++,d[y]++;
	Mat st,F;
	for(int i=1;i<=n;i++) {
		for(int j:e[i])st.a[i][j]=1;
		st.a[i][i+n]=1,st.a[i+n][i]=-d[i];
	}
	if(k<=2) {
		F=qp(st,k);
	}else {
		F=qp(st,2);
		for(int i=1;i<=n;i++)st.a[i+n][i]++;
		F=F*qp(st,k-2);
	}
	cout<<(F.a[1][n]+mod)%mod<<'\n';
	return 0;
}