#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
struct Matrix
{
	int n,m;
	vector<vector<long long>> mat; 
	Matrix(int s1,int s2):
		n(s1),m(s2),mat(n+1,vector<long long>(m+1)){}
	vector<long long>& operator [](int index)
	{
		return mat[index];
	}
	void display()
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
				cout<<mat[i][j]<<" ";
			cout<<endl;
		}
		cout<<"---------------"<<endl;
	}
	void setIdentity()
	{
		for(int i=1;i<=min(n,m);i++)
			mat[i][i]=1;
	}
};
Matrix operator *(Matrix a,Matrix b)
{
	Matrix tmp(a.n,b.m);
	for(int i=1;i<=tmp.n;i++)
		for(int j=1;j<=tmp.m;j++)
		{
			for(int k=1;k<=a.m;k++)
				tmp[i][j]+=a[i][k]*b[k][j]%P;
			tmp[i][j]=(tmp[i][j]%P+P)%P;
		}
	return tmp;
}
Matrix qpow(Matrix a,int k)
{
	int n=a.n;
	Matrix res(n,n);
	res.setIdentity();
	while(k)
	{
		if(k&1)res=res*a;
		a=a*a;
		k>>=1;
	}
	return res;
}
int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	Matrix trans(2*n,2*n),res(2*n,1);
	for(int i=1;i<=n;i++)
	{
		trans[i+n][i]=1;
		trans[i][i+n]=1;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		trans[u][v]=trans[v][u]=1;
		trans[u][u+n]--;
		trans[v][v+n]--;
	}
	res[1][1]=1;
	res=qpow(trans,k)*res;
	cout<<res[n][1]<<endl;
	return 0;
}