#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using matrix=vector <vector <int> >;
const int mod=998244353LL;
matrix add(matrix A,matrix B){
    int n=A.size(),m=A[0].size();
    matrix ret(n,vector <int>(m,0));
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++) ret[i][j]=(A[i][j]+B[i][j])%mod;
    }
    return ret;
}
matrix mul(matrix A,matrix B){
    int n=A.size(),m=B.size(),k=B[0].size();
    matrix ret(n,vector <int>(k,0));
    for (int i=0; i<n; i++){
        for (int j=0; j<k; j++){
            for (int l=0; l<m; l++) ret[i][j]=(ret[i][j]+A[i][l]*B[l][j])%mod;
        }
    }
    return ret;
}
matrix O,I;
vector <vector <matrix> > matmul(vector <vector <matrix> > A,vector <vector <matrix> > B){
    int n=A.size(),m=A[0].size(),k=B[0].size();
    vector <vector <matrix> > ret(n,vector <matrix>(m));
    for (int i=0; i<n; i++){
        for (int j=0; j<k; j++){
            ret[i][j]=O;
            for (int l=0; l<m; l++) ret[i][j]=add(ret[i][j],mul(A[i][l],B[l][j]));
        }
    }
    return ret;
}
vector <vector <matrix> > expo(vector <vector <matrix> > A,int p){
    int n=A.size();
    vector <vector <matrix> > ans(n,vector <matrix>(n));
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (i==j) ans[i][j]=I;
            else ans[i][j]=O;
        }
    }
    while (p){
        if (p&1ll) ans=matmul(ans,A);
        p>>=1ll;
        A=matmul(A,A);
    }
    return ans;
}
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    matrix M(n,vector <int>(n,0)),D(n,vector <int>(n,0));
    for (int i=0; i<n; i++) I.pb(vector <int>(n,0));
    for (int i=0; i<n; i++) I[i][i]=1;
    for (int i=0; i<n; i++) O.pb(vector <int>(n,0));
    while (m--){
        int u,v; cin>>u>>v;
        u--; v--;
        M[u][v]++; M[v][u]++;
        D[u][u]++; D[v][v]++;
    }
    vector <vector <matrix> > ans(2,vector <matrix>(2));
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) D[i][j]=(mod-D[i][j])%mod;
    ans[0][0]=M; ans[0][1]=add(D,I);
    ans[1][0]=I; ans[1][1]=O;
    vector <vector <matrix> > op=matmul(expo(ans,k-1),{{add(mul(M,M),D)},{M}});
    cout<<op[1][0][0][n-1]<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}