#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#define hh putchar('\n')
#define kg putchar(' ')
#define debug puts("debug")
#define int long long
//#define int __int128
namespace quickread{
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void write(T x){
		if(x<0) putchar('-'),x=~x+1;
		if(x>9) write(x/10);
		putchar(x%10^48);
	}
	inline string readstr(){
    	char ch=getchar();string str="";
		while(!isalnum(ch)) ch=getchar();
		while(isalnum(ch)){str+=ch;ch=getchar();}
		return str;
	}
	inline char readchar(){
		char ch=getchar();
		while(!isalnum(ch)) ch=getchar();
		return ch;
	}
	inline void putstr(string s){
		int len=s.length();
		for(int i=0;i<len;++i) putchar(s[i]);
	}
}
using namespace quickread;
const int mod=45989,N=2e5+10;
int n,m,tot=1,t,st,ed;
struct matrix{
	int val[160][160];
	void init(){
		for(int i=1;i<=tot;++i) for(int j=1;j<=120;++j)	val[i][j]=0;
	}
};
matrix operator * (const matrix &A,const matrix &B){
	matrix res;res.init();
	for(int i=1;i<=tot;++i)
		for(int j=1;j<=tot;++j)
			for(int k=1;k<=tot;++k)
				res.val[i][j]=(res.val[i][j]+A.val[i][k]*B.val[k][j]%mod)%mod;
	return res;
}
int nex[N],head[N],to[N];
void add(int u,int v){
	nex[++tot]=head[u];
	head[u]=tot;
	to[head[u]]=v;
} 
matrix ans ,pos; 
int res=0; 
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	read(n),read(m),read(t),read(st),read(ed);
	if(!t) write(0);
	++st,++ed;
	for(int i=1,u,v;i<=m;++i){
		read(u),read(v);++u,++v;
		add(u,v),add(v,u);
	}	
	pos.init(),ans.init();
	for(int i=head[st];i;i=nex[i]) ++ans.val[1][i];
	for(int i=1;i<=tot;++i)
		for(int j=head[i];j;j=nex[j])
			for(int k=head[to[j]];k;k=nex[k])
				if((j^k)^1) ++pos.val[j][k];
	--t;
	while(t){
		if(t&1) ans=ans*pos;
		pos=pos*pos;
		t>>=1;
	}
	for(int i=head[ed];i;i=nex[i])  res=(res+ans.val[1][i^1])%mod;
	write(res); 
	return 0;
}