#include<cstdio>

 #include<cstring>

 #include<iostream>

 const int maxn=;

 const double eps=1e-;

 const int modn=;

 int n,m,d,s,t;

 struct mat{

     long long e[][];

     mat(){ memset(e,,sizeof(e)); }

 };mat a;

 struct nod{

     int y;

     int f;

     int rev;

     int next;

 }e[];

 int tot=;

 int head[]={};

 mat Mul(mat x,mat y){

     mat z;

     for(int i=;i<=m*+;i++){

         for(int j=;j<=m*+;j++){

             for(int k=;k<=m*+;k++){

                 z.e[i][j]+=x.e[i][k]*y.e[k][j];

                 z.e[i][j]%=modn;

             }

         }

     }

     return z;

 }

 mat Pow(mat x,int k){

     mat z;

     for(int i=;i<=m*+;i++){

         z.e[i][i]=;

     }

     while(k>){

         if(k&){

             z=Mul(z,x);

         }

         x=Mul(x,x);

         k/=;

     }

     return z;

 }

 void init(int x,int y,int rev){

     e[++tot].y=y;

     e[tot].next=head[x];

     e[tot].rev=rev;

     head[x]=tot;

 }

 void dfs(int x,int v){

     int y;

     if(x==t){

         a.e[v][*m+]=;

     }

     for(int i=head[x];i;i=e[i].next){

         y=e[i].y;

         if(v!=e[i].rev){

             a.e[v][i]=;

         }

         if(!e[i].f){

             e[i].f=;

             dfs(y,i);

         }

     }

 }

 int main(){

     scanf("%d%d%d%d%d",&n,&m,&d,&s,&t);

     s+=,t+=;

     int x,y;

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

         scanf("%d%d",&x,&y);

         init(x+,y+,tot+);

         init(y+,x+,tot);

     }dfs(s,);

     mat z=Pow(a,d+);

     printf("%lld\n",z.e[][*m+]);

     return ;

 }