注意

PythonはPyPyを推奨します。

問題文

Moja王国には、街 11 から 街 NN までの NN 個の街 と、道 11 から 道 MM までの MM 個の道があります。 各道 jj は街 aja_j から街 bjb_j への一方通行の道であり、半日で移動することができます。

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

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

TT 日目まで( TT 日目も含む)に二人が会える確率を求め、 mod 998244353\mathrm{mod} ~ 998244353 で出力してください1

制約

  • 2N122 \le N \le 12
  • 1MN(N1)1 \le M \le N(N-1)
  • 1P,QN, PQ1 \le P, Q \le N, ~P \ne Q
  • 1T1061 \le T \le 10^{6}
  • 1aj,bjN, ajbj1 \le a_j, b_j \le N, ~ a_j \ne b_j
  • jj(aj,bj)(aj,bj)j \ne j' \Rightarrow (a_j ,b_j) \ne (a_{j'}, b_{j'})
  • 入力は全て整数

入力

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

NMPQTN \enspace M \enspace P \enspace Q \enspace T
a1b1a_1 \enspace b_1
\vdots
aMbMa_M \enspace b_M

出力

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

入出力例1

入力1
4 4 1 3 2
1 2
2 3
3 2
3 4
出力1
499122177

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

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

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

入出力例2

入力2
3 2 1 2 2
1 2
2 3
出力2
1

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

入出力例3

入力3
4 6 1 4 10
1 2
2 1
2 3
3 2
3 4
4 3
出力3
0

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

Footnotes

  1. この問題において求める確率は必ず有理数となり、またその値を互いに素な 22 つの整数 P,QP, Q を用いて PQ\frac{P}{Q} と表したとき、 R×QP (mod 998244353)R×Q \equiv P~(\mathrm{mod}~998244353) かつ 0R<9982443530≤R<998244353 を満たす整数 RR がただ 11 つ存在することが証明できます。この RR を出力してください。

Submit


Go (1.21)