题目描述

$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}$ の間を直接結ぶ辺が存在する
• 数列 $A$ の中に整数 $X\ (X≠S,X≠T)$ は偶数回出現する ( $0$ 回でも良い)

ただし、答えは非常に大きくなることがあるので、答えを $998244353$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを $998244353$ で割ったあまりを出力せよ。

题目大意

给你一个简单的无向图，有 $N$ 个顶点和 $M$ 条边。顶点从 $1$ 到 $N$ 编号，边从 $1$ 到 $M$ 编号，边 $i$ 连接顶点 $U_i$ 和顶点 $V_i$。 给你整数 $K,S,T$ 和 $X$。有多少个序列 $A = (A_0，A_1，\dots，A_K)$ 是否满足以下条件？

• 是介于 $1$ 和 $N$(含)之间的整数。
• $A_0$=$S$
• $A_K$=$T$
• 有一条边直接连接顶点 $A_i$ 和顶点 $A_{i+1}$。
• 整数 $X$($X$$≠$$S$,$X$$≠$$T$)在序列 $A$ 中出现偶数次(可能为零)。

由于答案可以很大，所以对 $998244353$ 取模。

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

4

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

提示

制約

• 入力は全て整数
• $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)$

Sample Explanation 1

- $(1,\ 2,\ 1,\ 2,\ 3)$ - $(1,\ 2,\ 3,\ 2,\ 3)$ - $(1,\ 4,\ 1,\ 4,\ 3)$ - $(1,\ 4,\ 3,\ 4,\ 3)$ の $4$ 個が条件を満たします。$(1,\ 2,\ 3,\ 4,\ 3)$ や $(1,\ 4,\ 1,\ 2,\ 3)$ は $2$ が奇数回出現するため、条件を満たしません。

Sample Explanation 2

グラフは連結であるとは限りません。

Sample Explanation 3

$998244353$ で割ったあまりを求めてください。