Description

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

Input

第一行: 五个整数 \(n, m, t, A, B\). 其中 \(n\) 表示学校里的路口的个数,\(m\) 表示学校 里的路的条数,\(t\) 表示 HH 想要散步的距离,\(A\) 表示散步的出发点, 而 \(B\) 则表示散步的 终点.

接下来 \(m\) 行, 每行一组 \(A_i, B_i\), 表示从路口 \(A_i\) 到路口 \(B_i\) 有一条路. 数据 保证 \(A_i \neq B_i\), 但不保证任意两个路口之间至多只有一条路相连接. 路口编号从 \(0\) 到 \(n - 1\). 同一行内所有数据均由一个空格隔开, 行首行尾没有多余空格. 没有多余 空行. 答案模 \(45989\).

Output

一行, 表示答案.

Sample Input

4 5 3 0 0
0 1
0 2
0 3
2 1
3 2

Sample Output

4

Data Range

对于 30% 的数据,\(n \leq 4, m \leq 10, t \leq 10\).

对于 100% 的数据,\(n \leq 20, m \leq 60, t \leq 2^30, 0 \leq A, B \lt n\).

Explanation

一个比较神的邻接矩阵乘法, 没怎么看懂~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 130;
const int modr = 45989;

struct edge
{
    int u, v;
    edge *next, *rev;
};
int ecnt;
edge *edges[maxn], epool[maxn];
void add_edge(int u, int v)
{
    edge *p = &epool[++ecnt],
         *q = &epool[++ecnt];
    p->u = u; p->v = v; p->next = edges[u]; edges[u] = p;
    q->u = v; q->v = u; q->next = edges[v]; edges[v] = q;
    p->rev = q; q->rev = p;
    return ;
}

struct matrix {
    lli val[maxn][maxn];
    matrix(void) {
        memset(val, 0, sizeof(val));
        return ; }
    matrix(int a) {
        memset(val, 0, sizeof(val));
        for (int i = 1; i <= ecnt; i++)
            val[i][i] = a;
        return ; }
    matrix& operator *= (matrix b) {
        static lli nv[maxn][maxn];
        memset(nv, 0, sizeof(nv));
        for (int i = 1; i <= ecnt; i++)
            for (int j = 1; j <= ecnt; j++) {
                nv[i][j] = 0;
                for (int k = 1; k <= ecnt; k++)
                    nv[i][j] += val[i][k] * b.val[k][j];
                nv[i][j] %= modr;
            }
        for (int i = 1; i <= ecnt; i++)
            for (int j = 1; j <= ecnt; j++)
                val[i][j] = nv[i][j];
        return *this;
    }
};
matrix operator ^ (matrix a, int b) {
    matrix res(1);
    for (int i = b; i > 0; i >>= 1, a *= a)
        if (i & 1)
            res *= a;
    return res;
}

int n, m, dist, A, B;

int main(int argc, char** argv)
{
    scanf("%d%d%d%d%d", &n, &m, &dist, &A, &B);
    ecnt = 1;
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        add_edge(a, b);
    }
    matrix matA, matB;
    for (edge *ep = edges[A]; ep; ep = ep->next) {
        matA.val[1][ep - &epool[0]] += 1;
    }
    for (int i = 2; i <= ecnt; i++)
        for (int j = 2; j <= ecnt; j++)
            if (epool[i].v == epool[j].u && epool[i].rev != &epool[j])
                matB.val[i][j] += 1;
    matA *= matB ^ (dist-1);
    lli res = 0;
    for (edge *ep = edges[B]; ep; ep = ep->next)
        res += matA.val[1][ep->rev - &epool[0]];
    res %= modr;
    printf("%lld\n", res);
    return 0;
}