問題文

ばるとーく王国には、$1$ から $N$ までの番号が振られた $N$ 個の街がある。
王国全体では $M$ 本の道があり、$i$ 番目の道は街 $u_i$ と街 $v_i$ を双方向に結ぶ。
各街は必ず $1$ つ以上の他の街と双方向に行き来可能な道で結ばれており、全ての街は道を使って互いに行き来できることが保証される。
また、各街の間には道は多くとも $1$ 本しかなく、ひとつの街だけで完結する道は存在しない。

冒険好きな少年ばる君は、$1$ 日目に街 $1$ にいる。
$2$ 日目以降の各日、ばる君は今いる街につながっている道の中から $1$ 本を等確率で選んで通り、その日に訪れる街へ移動する。
各日の移動は独立である。

ある日、王国の占い師がばる君にこう告げた。

「あなたは、$S$ 日目には必ず街 $A$ を訪れるでしょう。」

この予言が真であるとき、ばる君が $T$ 日目（$1 \leq T < S$）に街 $B$ を訪れた条件付き確率を $\textrm{mod }998244353$ で求めよ。
なお、本問題の制約下で、条件付き確率が一意に定義されることが保証される。

制約

• $2 \leq N \leq 50$
• $N-1 \leq M \leq \dfrac{N(N-1)}{2}$
• $1 \leq u_i,\ v_i \leq N$、$u_i \neq v_i$（自己ループをもたない）
• $i \neq j$ のとき $\{u_i,\ v_i\} \neq \{u_j,\ v_j\}$（多重辺をもたない）
• 各街は必ず $1$ つ以上の他の街と双方向に行き来可能な道で結ばれている
• 全ての街は道を使って互いに行き来できる（各街は連結している）
• $1 \leq A ,\ B \leq N$
• $1 \leq T < S \leq 10^{18}$
• ばる君が $S$ 日目に街 $A$ にいる確率は $0$ でないことが保証される
• 求める条件付き確率は分母が $998244353$ と互いに素な既約分数で表せる
• 入力はすべて整数

入力

$N\ M$  
$u_1\ v_1$　 
$u_2\ v_2$　 
$\vdots$   
$u_M\ v_M$   
$S\ T\ A\ B$   

出力

求める条件付き確率を $\textrm{mod }998244353$ で $1$ 行で出力せよ。
最後に改行すること。

サンプル

サンプル1

入力

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

出力

332748118

街は以下のような形をしています。

$1$ 日目に街 $1$ をスタートすると、日ごとの位置は以下のようになります。

• $1$ 日目：街 $1$ にいる（確率 $1$）
• $2$ 日目：街 $2$ にいる（確率 $1$）
• $3$ 日目：街 $1, 3, 4$ のいずれかにいる（各 $\dfrac{1}{3}$）
• $4$ 日目：街 $2$ にいる（確率 $1$）
• $5$ 日目：街 $1, 3, 4$ のいずれかにいる（各 $\dfrac{1}{3}$）

よって、計算は以下のようになります。　

分子 $= P(\text{3日目に街3} \land \text{5日目に街1}) = \dfrac{1}{3} \times \dfrac{1}{3} = \dfrac{1}{9}$（今回のケースではこの2つの事象がたまたま独立であるためこの計算が成り立ちます）

分母 $ = P(\text{5日目に街1}) = \dfrac{1}{3}$

これから、求める条件付き確率は$\dfrac{\frac{1}{9}}{\frac{1}{3}} = \dfrac{1}{3}$と求まります。

$3 \times 332748118 \equiv 1 \pmod{998244353}$ より、出力は $332748118$ となります。

10 20
1 5
1 7
1 9
1 10
2 5
2 6
2 7
3 4
3 6
4 5
4 6
4 7
4 8
4 9
4 10
5 7
6 8
6 10
8 9
8 10
500 100 1 1

629589520

10 45
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 5
4 6
4 7
4 8
4 9
4 10
5 6
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 8
7 9
7 10
8 9
8 10
9 10
1000000000000000000 333333333333333333 3 8

312640670