配点 : $500$ 点

問題文

$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 \neq S,X \neq T)$ は偶数回出現する ( $0$ 回でも良い)

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

制約

• 入力は全て整数
• $2 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq K \leq 2000$
• $1 \leq S,T,X \leq N$
• $X \neq S$
• $X \neq T$
• $1 \leq U_i
• $i \neq j$ ならば $(U_i, V_i) \neq (U_j, V_j)$

入力

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

$N$ $M$ $K$ $S$ $T$ $X$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

出力

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

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

4

• $(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$ が奇数回出現するため、条件を満たしません。

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$ で割ったあまりを求めてください。