AT_abc244_e [ABC244E] King Bombee

[problemUrl]: https://atcoder.jp/contests/abc244/tasks/abc244_e $ 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 $ で割ったあまりを出力せよ。

### 制約 - 入力は全て整数 - $ 2\