// 从未在意的名字永远不会被提起 雪葉/鹤见江野

/*
+
++
+++
++++
+++++
++++++
+++++++
++++++++
+++++++++
++++++++++
+++++++++++
++++++++++++
+++++++++++++
++++++++++++++
+++++++++++++++
++++++++++++++++
+++++++++++++++++
++++++++++++++++++
+ +++++++++++++++++
+  ++++++++++++++ ++
+   +++++++++++++  ++
+    ++++++++++++   ++
+     +++++++++++    ++
+      ++++++++++     ++
+       +++++++++      ++
+        ++++++++       ++
+         +++++++++++++++++
+          +++++++++++++++++
+           ++++++++++++++
+            +++++++++++
+             ++++++++
+              +++++
+               ++
+               +
+               +
+              ++
+             +++
+            ++++
+           +++++
+           +++++
+           +++++
+           +++++
+     +     +++++
+    +++    +++++
+   ++ ++   +++++
+  ++   ++  +++++
+ ++  +  ++ +++++
+++  +++  +++++++
++  ++ ++  ++++++
 
 
 ++++++++      +++++++++++     +++      +++        ++++++++        ++++++++
+++++++++     +++++++++++++    +++      +++       +++    +++      +++    +++
+++          +++   +++   +++   +++      +++      +++   ++++++    +++      +++
+++          +++   +++   +++   +++      +++      +++ +++  +++           +++
+++          +++   +++   +++   +++ ++   +++ ++   ++++++   +++         +++
+++++++++    +++   +++   +++   +++ ++   +++ ++    +++    +++        +++    ++
 ++++++++    +++   +++   +++   +++++    +++++      ++++++++       +++++++++++
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define rg(x) for(int i=1;i<=(x);i++){
#define rg_(i,x) for(int i=1;i<=(x);i++){
#define gr }
#define rrg(x) for(int i=0;i<(x);i++)
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
#define int long long
#define newe(n) struct Edge{int v,w,nxt;}e[n*2+5];\
typedef int arr[n+5];\
arr h;\
int cnt=1;\
inline void addedge(int u,int v,int w){e[cnt]=(Edge){v,w,h[u]};h[u]=cnt++;}
#define mgs int fa[1<<22],sz[1<<22],t[1<<22];\
inline int f(int x){return x==fa[x]?x:fa[x]=f(fa[x]);}\
inline int u(int x,int y)\
{\
    int fx=f(x),fy=f(y);\
    if(fx==fy)return 0;\
    if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;\
    fa[fx]=fy,sz[fy]+=sz[fx];\
    return 1;\
}
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
inline int re1d()
{
    char c=getchar();
    while(c<48||c>49)c=getchar();
    return c&1;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
const int M=45989;
class array{
	public:
//	int n,m;
	int n,m;
	int a[252][252];
	array(){memset(a,0,sizeof(a));}
	array operator*(array b)
	{
		if(m!=b.n)
		{
			puts("you are too naive.");
			print();
			b.print();
			exit(0);
		}
		array c;
//		memset(c.a,0,sizeof(c.a));
		c.n=n;
		c.m=b.m;
		for(int i=0;i<n;i++)
			for(int j=0;j<b.m;j++)
				for(int k=0;k<m;k++)
					c.a[i][j]+=a[i][k]*b.a[k][j]%M,c.a[i][j]%=M;
					//c.a[i][j]=max(c.a[i][j],a[i][k]+b.a[k][j]);
		return c;
	}
	array operator=(array b)
	{
		n=b.n,m=b.m;
		rrg(n)rg_(j,m)a[i][j-1]=b.a[i][j-1];gr
		return *this;
	}
	void print()
	{
		rg(n)rg_(j,m)odb(a[i-1][j-1]);gr puts("");gr puts("");
	}
	void clear(int s)
	{
//		rrg(m)a[s][i]=0;
		rrg(n)a[i][s]=0;
	}
};
int u[10005],v[10005];
signed main()
{
	array x;
	int n=read(),m=read(),T=read(),a=read(),b=read(),cc=0;x.n=x.m=m+1<<1;
	u[1]=n,v[1]=a;
	rg(m)u[i<<1]=read(),v[i<<1]=read();u[i<<1|1]=v[i<<1],v[i<<1|1]=u[i<<1];gr
	for(int i=1;i<=(m<<1|1);i++)for(int j=1;j<=(m<<1|1);j++)if((i!=j)&&((i^j)!=1))if(v[i]==u[j])x.a[i][j]=1;
//	x.print();
	array ans;
	ans.n=ans.m=m+1<<1;
	rrg(ans.n)ans.a[i][i]=1;
//	ans.print();
	while(T)
	{
		if(T&1)ans=ans*x;
		x=x*x;
		T>>=1;
	}
//	ans.print();
	int qwq=0;
	for(int i=1;i<=(m<<1|1);i++)if(v[i]==b)qwq+=ans.a[1][i];
	oldl(qwq);
	return 0;
}