問題文

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

制約

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

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

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