#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int mod=45989;

const int nmax=25;

const int maxn=125;

int N,M,T,A,B;

int U[maxn],V[maxn],id[maxn],f[maxn];

struct matrix{

	int a[maxn][maxn];

	matrix(){

		clr(a,0);

	}

	matrix operator*(const matrix &o)const {

	    matrix rhs;

	    REP(i,1,M) REP(j,1,M) REP(k,1,M) rhs.a[i][j]=(rhs.a[i][j]+a[i][k]*o.a[k][j])%mod;

	    return rhs;

	}

}a,b;

int main(){

	N=read(),M=read(),T=read(),A=read(),B=read();T--;

	REP(i,1,M){

		U[i]=read(),V[i]=read();U[i+M]=V[i],V[i+M]=U[i];id[i]=id[i+M]=i;

	}

	M*=2;

	REP(i,1,M) REP(j,1,M) if(id[i]!=id[j]&&V[i]==U[j])  b.a[i][j]=1;

	REP(i,1,M) a.a[i][i]=1;

	while(T) {

		if(T&1) a=a*b;

		b=b*b;T>>=1;

	}

	REP(i,1,M) if(U[i]==A) f[i]=1;

	int ans=0;

	REP(i,1,M) if(V[i]==B)

	  REP(j,1,M) ans=(ans+a.a[j][i]*f[j])%mod;

	printf("%d\n",ans);

	return 0;

}

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的 路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。 接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N − 1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。

一行，表示答案。

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。 对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Day1