#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
#define bg begin
cs int RLEN=1<<22|1;
char ibuf[RLEN],*ib,*ob;
inline char gc(){
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}

cs int mod=998244353;

inline int add(int a,int b){return (a+b)>=mod?(a+b-mod):(a+b);}
inline int dec(int a,int b){return (a<b)?(a-b+mod):(a-b);}
inline int mul(int a,int b){static ll r;r=(ll)a*b;return (r>=mod)?(r%mod):r;}
inline void Add(int &a,int b){a=(a+b)>=mod?(a+b-mod):(a+b);}
inline void Dec(int &a,int b){a=(a<b)?(a-b+mod):(a-b);}
inline void Mul(int &a,int b){static ll r;r=(ll)a*b;a=(r>=mod)?(r%mod):r;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
inline int fix(ll x){x%=mod;return (x<0)?x+mod:x;}

cs int N=205;
int L;
struct mat{
    int a[N][N];
    mat(){memset(a,0,sizeof(a));}
    friend inline mat operator *(cs mat &a,cs mat &b){
        mat c;
        for(int i=1;i<=L;i++)
        for(int k=1;k<=L;k++)
        for(int j=1;j<=L;j++){
            Add(c.a[i][j],mul(a.a[i][k],b.a[k][j]));
        }
        return c;
    }
}A;
mat pow(mat A,mat B,int b){
    for(;b;b>>=1){
        if(b&1){
            B=B*A;
        }
        A=A*A;
    }
    return B;
}
int n,m,kk;
int e[N][N];
int main(){
    #ifdef Stargazer
    freopen("1.in","r",stdin);
    #endif
    n=read();
    m=read();
    kk=read();

    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        A.a[u][v]++;
        A.a[v][u]++;
        e[u][v]=e[v][u]=1;
        Dec(A.a[u+n][u],1);
        Dec(A.a[v+n][v],1);
    }
    for(int i=1;i<=n;i++)Add(A.a[i+n][i],1);
    for(int i=1;i<=n;i++)A.a[i][i+n]=1;
    L=2*n;
    mat B;
    for(int i=1;i<=n;i++)B.a[1][i+n]=e[1][i];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)if(e[j][i])B.a[1][i]+=e[1][j];
    B.a[1][1]=0;
    if(kk==1){
        cout<<A.a[1][n+n]<<'\n';
    }
    else if(kk==2){
        cout<<A.a[1][n]<<'\n';
    }
    else{
        A=pow(A,B,kk-2);
        cout<<A.a[1][n]<<'\n';
    }

}