Random Walkers

注意

PythonはPyPyを推奨します。

問題文

Moja王国には、街 $1$ から 街 $N$ までの $N$ 個の街 と、道 $1$ から 道 $M$ までの $M$ 個の道があります。 各道 $j$ は街 $a_j$ から街 $b_j$ への一方通行の道であり、半日で移動することができます。

はじめ、みーとみさんは街 $P$ に、お茶の葉さんは街 $Q$ にいます。 二人は $T$ 日後に王国内で会うことを約束していますが、どの街で会うのかを決め忘れてしまいました。 連絡手段を持っていないため、二人はそれぞれ $T$ 日間以下のように王国内を歩き回って相手を探します。

• $t ~(= 1,\dots,T)$ 日目の午前、前日までに出会えていない場合
  • 今いる街が始点となる道があればそれらから一様ランダムに一つ道を選んで移動し、終点の街に午後到着します。
  • そのような道がなければ、今いる街に留まります。
• $t$ 日目の午後（移動があった場合は二人の到着後）
  • 二人が同じ街にいる場合には会うことができ、以後相手を探すのをやめます。
  • 二人が異なる街にいる場合は、翌日また同様に相手を探します。

$T$ 日目まで（ $T$ 日目も含む）に二人が会える確率を求め、 $\mathrm{mod} ~ 998244353$ で出力してください¹。

制約

• $2 \le N \le 12$
• $1 \le M \le N(N-1)$
• $1 \le P, Q \le N, ~P \ne Q$
• $1 \le T \le 10^{6}$
• $1 \le a_j, b_j \le N, ~ a_j \ne b_j$
• $j \ne j' \Rightarrow (a_j ,b_j) \ne (a_{j'}, b_{j'})$
• 入力は全て整数

入力

入力は以下の形式で与えられます。

出力

答えを出力してください。

入出力例１

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

499122177

はじめ、みーとみさんは街 $1$ に、お茶の葉さんは街 $3$ におり、以後以下のように移動します。

• $1$ 日目の移動後、みーとみさんは街 $2$ におり、お茶の葉さんは街 $2$ または街 $4$ にいるため、確率 $\frac{1}{2}$ で会うことができます。
• $1$ 日目に会えなかった場合、$2$ 日目にみーとみさんは街 $3$ に移動し、お茶の葉さんは街 $4$ に留まるので、$2$ 日目に会うことはありません。

よって求める確率は $\frac{1}{2}$ となるため、$\mathrm{mod}~998244353$ をとって $499122177$ を出力します。

入出力例２

3 2 1 2 2
1 2
2 3

1

二人は必ず会うことができます。

入出力例３

4 6 1 4 10
1 2
2 1
2 3
3 2
3 4
4 3

0

二人は絶対に会うことができません。