题目描述

给定一个具有 $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≠S,X≠T)$ 在序列 $A$ 中出现的次数（可能为零）是偶数。

由于答案可能非常大，计算答案对 $998244353$ 取模的结果。

约束条件

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

输入

从标准输入中以以下格式给出输入：

$N$ $M$ $K$ $S$ $T$ $X$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出

将答案对 $998244353$ 取模后输出。

样例输入 1

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

样例输出 1

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$ 出现的次数是奇数。

样例输入 2

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

样例输出 2

0

图不一定连通。

样例输入 3

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

样例输出 3

952504739

将答案对 $998244353$ 取模后输出。