#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 400;
const int mod = 45989;
struct Matrix {
    int n, m;
    int a[maxn][maxn];
    Matrix() { memset(a, 0, sizeof a); }
    Matrix(int _n, int _m) {
        n = _n;
        m = _m;
        memset(a, 0, sizeof a);
    }
    
    void scan() {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) cin >> a[i][j];
    }
    void print() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) cout << a[i][j] << ' ';
            cout << endl;
        }
    }
};

Matrix mul(Matrix &a, Matrix &b) {
    Matrix res(a.n, b.m);
    for (int i = 0; i < a.n; i++)
        for (int j = 0; j < b.m; j++)
            for (int k = 0; k < a.m; k++)
                (res.a[i][j] += a.a[i][k] * b.a[k][j] % mod) %= mod;
    return res;
}

Matrix Pow(Matrix &base, int n) {
    Matrix res(base.n, base.n);
    for (int i = 0; i < res.n; i++) res.a[i][i] = 1;
    for (; n; n >>= 1) {
        if (n & 1) res = mul(res, base);
        base = mul(base, base);
    }
    return res;
}
struct node
{
	int u,v;
}edge[maxn];
int cnt;
void add(int u,int v)
{
	cnt++;
	edge[cnt].u=u;
	edge[cnt].v=v;
}
signed main() {
    //freopen("lost.in", "r", stdin);
    //freopen("lost.out", "w", stdout);
    int n,m,t,a,b;
    cin>>n>>m>>t>>a>>b;
    for(int i=1;i<=m;i++)
    {
    	int x,y;
    	cin>>x>>y;
    	add(x,y);
    	add(y,x);
	}
    if(t==0) {cout<<0;return 0;}
	Matrix base(cnt,cnt);
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=cnt;j++)
		{
			if(i!=(j^1))
			{
				if(edge[i].v==edge[j].u)
				base.a[i-1][j-1]=1;
			}
		}
	}
//	base.print();
	base=Pow(base,t-1);
 //   cout<<endl;
	//base.print();
	long long ans=0;
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=cnt;j++)
		{
			if(edge[i].u==a&&edge[j].v==b)
			{
				ans+=base.a[i-1][j-1];
				ans%=mod;
			}
		}
	}
	cout<<ans<<endl;
    return 0;
}