# SDOI2009[HH去散步]

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-25

DESCRIPTION:

*/

#include <iostream>

#include <string.h>

using namespace std;

const int MAXN=20;

const int MAXM=60;

const int MODER=45989;

int N,M,A,B;

long long int t;

int a[MAXM*2],b[MAXM*2];

typedef unsigned int matrix[MAXM*2][MAXM*2];

int K;

matrix mA,mB,mBB,mC;

void mul(matrix A,matrix B,matrix C)

{

for (int i=0;i<K;i++)

for (int j=0;j<K;j++)

{

C[i][j]=0;

for (int k=0;k<K;k++)

C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MODER;

}

}

void power(matrix A,long long int n,matrix B)

{

matrix a,b,ab,aa;

matrix* bp=&b;

matrix* ap=&a;

matrix* abp=&ab;

matrix* aap=&aa;

matrix* swap;

memcpy((*ap),A,sizeof(matrix));

memset((*bp),0,sizeof(matrix));

for (int i=0;i<K;i++) (*bp)[i][i]=1;

while (n)

{

if (n&1)

{

mul(*bp,*ap,*abp);

swap=bp;

bp=abp;

abp=swap;

}

mul(*ap,*ap,*aap);

swap=ap;

ap=aap;

aap=swap;

n>>=1;

}

memcpy(B,*bp,sizeof(matrix));

}

int main()

{

cin>>N>>M>>t>>A>>B;

for (int i=0;i<M;i++)

cin>>a[i]>>b[i],

a[i+M]=b[i],b[i+M]=a[i];

//f[T][EDGE]表示走了T,在最后走的是EDGE的方案数

//f[1][EDGE]=1 v(EDGE)=A

//f[T][EDGE]=sum{f[T-1][EDGE’];v(EDGE)=u(EDGE’) and EDGE!=EDGE’的反向边}

K=M*2;

for (int i=0;i<K;i++)

if (a[i]==A) mA[0][i]=1;

for (int i=0;i<K;i++)

for (int j=0;j<K;j++)

if (b[i]==a[j]&&i!=j+M&&j!=i+M)

mB[i][j]=1;

power(mB,t-1,mBB);

for (int i=0;i<1;i++)

for (int j=0;j<K;j++)

for (int k=0;k<K;k++)

mC[i][j]=(mC[i][j]+mA[i][k]*mBB[k][j])%MODER;