#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;

mt19937 rng(time(NULL));

const int mod=998244353;
int add(int a,int b){
    a+=b;
    if(a>=mod)
        a-=mod;
    return a;
}
int sub(int a,int b){
    a-=b;
    if(a<0)
        a+=mod;
    return a;
}
int mul(int a,int b){
    return (long long)a*b%mod;
}
vector<vector<int>> mul(vector<vector<int>> &a,vector<vector<int>> &b){
	vector<vector<int>> ans(sz(a),vector<int>(sz(b[0])));
	for(int i=0;i<sz(a);i++){
		for(int j=0;j<sz(b[0]);j++){
			for(int k=0;k<sz(a[0]);k++){
				ans[i][j]=add(ans[i][j],mul(a[i][k],b[k][j]));
			}
		}
	}
	return ans;
}
vector<vector<int>> pwrmod(vector<vector<int>> a,int k){
	vector<vector<int>> ans=a;
	k--;
	for(;k;k>>=1,a=mul(a,a))
		if(k&1)
			ans=mul(ans,a);
	return ans;
}
int main()
{
	int n,m,k;
	cin >> n >> m >> k;
	vector<vector<int>> mat(2*n,vector<int>(2*n));
	vector<vector<int>> start(1,vector<int>(2*n));
	vector<int> deg(n);
	vector<vector<int>> graf(n);
	for(int i=0;i<m;i++){
		int u,v;
		cin >> u >> v;
		u--;v--;
		mat[u][v]=mat[v][u]=1;
		deg[u]++;
		deg[v]++;
		graf[u].pb(v);
		graf[v].pb(u);
	}
	for(int i=0;i<n;i++){
		mat[i][i+n]=1;
		mat[i+n][i]=mod-deg[i]+1;
	}
	for(auto p:graf[0]){
		start[0][n+p]=1;
	}
	for(auto p:graf[0]){
		for(auto d:graf[p]){
			start[0][d]++;
		}
	}
	start[0][0]=0;
	k--;
	if(k==0){
		printf("%i\n",start[0][n+n-1]);
		return 0;
	}
	vector<vector<int>> st=pwrmod(mat,k);
	start=mul(start,st);
	printf("%i\n",start[0][n+n-1]);
	return 0;
}