You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

最近cls玉玉了，为了释放些许压力 cls 决定在一个无向图上进行游走。

给出 $n$ 个点，$m$ 条边的无向图，cls要从点$S$出发，经过 $K$条边，到达点$T$ 的路径方案数。但这个问题有点简单，cls增加一个条件，这种路径经过点$X$的次数必须是偶数次。求方案数。由于答案很大，结果对 $998244353$ 取模。

Format

Input

第一行$6$个整数，$N, M, K, S, T, X$

接下来$M$行，每行两个整数 $u_i, v_i$ 表示一条无向边。

Output

输出一个整数表示答案

Samples

样例输入 1

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

样例输出 1

4

样例解释 1

从点1出发，到达3，经过4条边，且经过2的次数为偶数的路径有4条

1 -> 2 -> 1 -> 2 -> 3

1 -> 2 -> 3 -> 2 -> 3

1 -> 4 -> 1 -> 4 -> 3

1 -> 4 -> 3 -> 4 -> 3

样例输入 2

10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2

样例输出 2

952504739

$30 \%$ 的数据满足 $N, M, K \leq 8, 1 \leq S, T, X \leq n$

$60 \%$ 的数据满足 $N, M, K \leq 100, 1 \leq S, T, X \leq n$

$100 \%$ 的数据满足 $N, M, K \leq 2000, 1 \leq S, T, X \leq n$