#include<cstdio>

#include<iostream>

#include<cstring>

#define R register int

using namespace std;

//你弱，有什么资格休息

#define ull unsigned long long

#define ll long long

#define pause (for(R i=1;i<=10000000000;++i))

#define In freopen("NOIPAK++.in","r",stdin)

#define Out freopen("out.out","w",stdout)

namespace Fread {

static char B[<<],*S=B,*D=B;

#ifndef JACK

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

#endif

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    if(ch==EOF) return EOF; do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

} inline bool isempty(const char& ch) {return (ch<=||ch>=);}

inline void gs(char* s) {

    register char ch; while(isempty(ch=getchar()));

    do *s++=ch; while(!isempty(ch=getchar()));

}

} using Fread::g; using Fread::gs;

namespace Luitaryi {

const int N=,M=;

int n,m,p,S,T,cnt=-,x[N],y[N];

int a[N][N],s[][N],ans[][N],anss;

inline void mul(int a[][N],int b[][N]) { R tmp[N][N]; memset(tmp,,sizeof(tmp));

    for(R i=;i<=cnt;++i) for(R k=;k<=cnt;++k) for(R j=;j<=cnt;++j)

        (tmp[i][j]+=1ll*a[i][k]*b[k][j]%M)%=M;

    memcpy(a,tmp,sizeof(tmp));

}

inline void qpow(int p) {

    R ret[N][N]; memset(ret,,sizeof(ret));

    for(R i=;i<=cnt;++i) ret[i][i]=;

    for(;p;p>>=,mul(a,a)) if(p&) mul(ret,a);

    memcpy(a,ret,sizeof(ret));

}

inline void main() {

    n=g(),m=g(),p=g(),S=g(),T=g();

    for(R i=;i<=m;++i) {

        R u=g(),v=g();

        x[++cnt]=u,y[cnt]=v;

        x[++cnt]=v,y[cnt]=u;

    } for(R i=;i<=cnt;++i) for(R j=;j<=cnt;++j) if(i!=(j^)&&y[i]==x[j]) a[i][j]+=;

    for(R i=;i<=cnt;++i) if(x[i]==S) s[][i]=;

    qpow(p-); for(R i=;i<=cnt;++i) for(R j=;j<=cnt;++j) (ans[][j]+=1ll*s[][i]*a[i][j]%M)%=M;

    for(R i=;i<=cnt;++i) if(y[i]==T) (anss+=ans[][i])%=M; printf("%d\n",anss);

}

}

signed main() {

    Luitaryi::main();

}