题目内容

一家物流企业共有 $N$ 座中转站，各站依次标记为 $1$ 至 $N$。站点间铺设了若干运输线路，每条线路都只支持指定方向的运输。

现已获得该网络的全部线路资料，需要回答一次运输路径计数问题。

请统计从中转站 $S$ 启程、沿线路移动恰好 $L$ 次后停在中转站 $T$ 的路径总数。同一站点可以在途中反复到访，已经走过的线路也能够再次使用。只要经过的站点序列有一处不同，就视为两条不同路径。

输入描述

• 首行给出两个整数 $N$、$M$，依次代表站点总数和线路总数。
• 下一行给出三个整数 $S$、$T$、$L$，依次代表出发站、目的站和必须使用的线路条数。
• 随后有 $M$ 行，各行给出整数 $u$、$v$，说明存在一条由站点 $u$ 驶向站点 $v$ 的线路。

约束

• $1 \le N \le 20$。
• $1 \le M \le 200$。
• $1 \le L \le 10$。
• $1 \le u,v \le N$。
• $1 \le S,T \le N$。
• $u \ne v$，即线路不会连接站点自身。
• 任意一对有序站点之间至多存在一条线路。

输出描述

输出一个整数，表示符合要求的路径总数；若没有可行路径，则输出 $0$。答案无需取模。

样例1

输入：

5 7
2 5 4
2 3
3 2
3 4
4 3
3 5
2 5
5 1

输出

2

解释：

从站点 $2$ 启程，使用 $4$ 条线路后停在站点 $5$，有以下两种走法：

• $2 \to 3 \to 2 \to 3 \to 5$。
• $2 \to 3 \to 4 \to 3 \to 5$。

两种走法都再次到访了站点 $3$。

样例2

输入：

6 6
2 6 2
2 1
1 6
2 4
4 6
2 5
5 6

输出：

3

解释：

由站点 $2$ 出发，使用 $2$ 条线路到站点 $6$，可选择 $2 \to 1 \to 6$、$2 \to 4 \to 6$ 或 $2 \to 5 \to 6$。

样例 3

输入：

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

输出：

0

解释：

站点 $4$ 没有直接驶向站点 $1$ 的线路，因此只使用 $1$ 条线路无法抵达目的站。