#include <bits/stdc++.h>
using namespace std;
const int p=998244353;
struct matrix
{
	int a[311][311],r,c;
	matrix(){memset(a,0,sizeof(a));r=c=0;}
	matrix(int _r,int _c){r=_r;c=_c;memset(a,0,sizeof(a));}
};
matrix operator*(matrix a,matrix b)
{
	matrix c(a.r,b.c);
	for(int i=0;i<a.r;++i)
	{
		for(int j=0;j<b.c;++j)
		{
			__int128 tt=0;
			for(int k=0;k<a.c;++k)
			{
				tt+=1ll*a.a[i][k]*b.a[k][j];
			}
			c.a[i][j]=tt%p;
		}
	}
	return c;
}
matrix qpow(matrix bs,int ex)
{
	matrix ans(bs.r,bs.c);
	for(int i=0;i<bs.r;++i)ans.a[i][i]=1;
	while(ex)
	{
		if(ex&1)ans=ans*bs;
		bs=bs*bs;ex>>=1;
	}
	return ans;
}
int n,m,k;
vector<int> G[311];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;++i)
	{
		int u,v;scanf("%d%d",&u,&v);
		G[u].push_back(v);G[v].push_back(u);
	}
	matrix E(3*n+1,3*n+1);
	for(int i=1;i<=n;++i)
	{
		for(int v:G[i])
		{
			E.a[i][v]=1;
		}
	}
	for(int i=1;i<=n;++i)
	{
		E.a[i][i+n]=-1;
		E.a[i+n][i+2*n]=E.a[i+2*n][i+n]=-1;
		E.a[i+n][i]=(int)G[i].size();
		for(int v:G[i])E.a[i+2*n][v]=1;
	}
	// printf("E:\n");
	// for(int i=1;i<=2*n;++i)
	// {
	// 	for(int j=1;j<=2*n;++j)printf("%d ",E.a[i][j]);putchar(10);
	// }
	E=qpow(E,k);
	// printf("E:\n");
	// for(int i=1;i<=2*n;++i)
	// {
	// 	for(int j=1;j<=2*n;++j)printf("%d ",E.a[i][j]);putchar(10);
	// }
	printf("%d\n",(E.a[1][n]%p+p)%p);
}