国王邦比

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$,边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。

给定整数 $K$, $S$, $T$ 和 $X$。求满足以下条件的序列 $A = (A_0, A_1, \dots, A_K)$ 的个数:

• $A_i$ 是 $1$ 到 $N$(含端点)之间的整数。
• $A_0 = S$
• $A_K = T$
• 存在一条边直接连接顶点 $A_i$ 和顶点 $A_{i+1}$。
• 整数 $X\ (X \neq S, X \neq T)$ 在序列 $A$ 中出现偶数次(可以为 $0$ 次)。

由于答案可能非常大,请输出答案对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出:

N M K S T X
U_1 V_1
U_2 V_2
⋮
U_M V_M

输出格式

输出答案对 $998244353$ 取模的结果。

样例

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

4

以下 $4$ 个序列满足条件:

$(1, 2, 1, 2, 3)$

$(1, 2, 3, 2, 3)$

$(1, 4, 1, 4, 3)$

$(1, 4, 3, 4, 3)$

另一方面,$(1, 2, 3, 4, 3)$ 和 $(1, 4, 1, 2, 3)$ 不满足条件,因为 $2$ 出现了奇数次。

6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5

0

图不一定是连通的。

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

952504739

输出答案对 $998244353$ 取模的结果。

数据范围

• 输入中的所有值均为整数。
• $2 \le N \le 2000$
• $1 \le M \le 2000$
• $1 \le K \le 2000$
• $1 \le S, T, X \le N$
• $X \neq S$
• $X \neq T$
• $1 \le U_i \lt V_i \le N$
• 若 $i \neq j$,则 $(U_i, V_i) \neq (U_j, V_j)$。