乍一看矩阵水题，然后发现不能走回头路。
于是改一下把边当做点，把点当作转移，转移的时候就可以避免走过去就走回来的情况了。
说好的复习会考呢？
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define _l (long long int)
const int mod = 45989;
const int maxn = 123;
class matrix {
public:
int n, a[maxn][maxn];
inline matrix() {
}
inline matrix(int n0, bool one = 0) {
n = n0;
memset(a, 0, sizeof(a));
if (one)
for (int i = 0; i < n; ++ i)
a[i][i] = 1;
}
void operator =(const matrix& x) {
n = x. n;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
a[i][j] = x. a[i][j];
}
matrix operator *(const matrix& x) {
matrix r(n);
for (int k = 0; k < n; ++ k)
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
r. a[i][j] = (r. a[i][j] + _l a[i][k] * x. a[k][j] % mod) % mod;
return r;
}
};
struct edge {
int a, b;
inline edge(int a0 = 0, int b0 = 0) {
a = a0, b = b0;
}
};
#define nin(x) ((x)<<1)
#define nou(x) (((x)<<1)|1)
matrix a, s;
int n, m, t, x, y;
edge e[maxn];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d%d%d%d", &n, &m, &t, &x, &y);
n = 0;
for (int i = 0; i < m; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
e[n ++] = edge(u, v);
e[n ++] = edge(v, u);
}
e[n ++] = edge(-1, x);
e[n ++] = edge(y, -2);
a = matrix(n);
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
if (i != j && (i ^ j ^ 1) && e[i]. b == e[j]. a)
a. a[i][j] = 1;
s = matrix(n, 1);
for (++ t; t; t >>= 1, a = a * a)
if (t & 1)
s = s * a;
printf("%d\n", s. a[n - 2][n - 1]);
}