白兔が迷宮に入りました。迷宮は $n$ 個の頂点と $m$ 本の辺からなる有向グラフであり、多重辺や自己ループが存在する可能性があります。頂点は $1$ から $n$ まで番号が振られており、始点は $S$、終点は $T$ です。どの頂点から出発しても $T$ に到達する経路が存在することが保証されています。
迷宮の各辺にはモンスターが配置されており、モンスターは $0$ または $1$ の $2$ 種類です。白兔はスコアを持っており、初期値は $0$ です。白兔がある辺を通るたびに、以下のことが起こります。
- その辺のモンスターが $1$ の場合、白兔はそのモンスターを倒してスコアを $1$ 増やし、その辺の終点へ移動します。
- その辺のモンスターが $0$ の場合、白兔はそのモンスターによって気絶させられます。モンスターは白兔を殺すことはありませんが、それまでに獲得したスコアをすべて $0$ にリセットし、白兔をその辺の終点へ移動させます。
辺を通るたびにその辺のモンスターは復活するため、白兔が同じ辺を複数回通るたびにモンスターの効果が繰り返し発生します。
白兔は迷宮の構造を知らないため、ランダムウォークを行うことにしました。すなわち、$S$ から出発し、現在の頂点から出る辺を独立に等確率で選択して移動し、対応する辺のモンスターの効果を発生させてその辺の終点に到達します。白兔が初めて $T$ に到達した時点で、ウォークは終了します。
このグラフの構造と各辺のモンスターの種類が与えられます。ウォーク終了時のスコアを確率変数 $X$ とするとき、以下の $2$ つの問いに答えてください。
- $X$ の期待値はいくらか。
- $X$ の分散はいくらか。
白兔は実数を好まないため、$998244353$ で割った余りを出力してください。問題の条件下において、答えは必ず有理数となり、既約分数形式にしたとき分母は $998244353$ の倍数にならないことが示せます。
入力
入力は標準入力から与えられます。
入力の最初の行には、$4$ つの整数 $n, m, S, T$ が含まれており、それぞれ迷宮の頂点数、辺数、始点、終点を表します。
続く $m$ 行には、それぞれ $3$ つの整数 $x, y, o$ が含まれており、$x$ から $y$ への有向辺と、その辺上のモンスターの種類を表します。
出力
標準出力に結果を出力します。
$1$ 行に $2$ つの整数を出力してください。最初の整数はスコアの期待値、 $2$ 番目の整数はスコアの分散を表します。
入出力例
入力 1
2 2 1 2 1 1 1 1 2 1
出力 1
2 2
注記 1
頂点 $1$ からは自己ループが $1$ つと、頂点 $2$ へ向かう辺が $1$ つあります。各辺の $o = 1$ であるため、スコアはランダムウォークの歩数と等しくなります。
$x > 0$ に対して、最終的なスコアが $x$ となるのは、白兔が最初に頂点 $1$ で自己ループを $x-1$ 回通り、 $x$ 回目に頂点 $2$ に到達する場合のみです。したがって、スコアが $x$ となる確率は $2^{-x}$ です。ゆえに期待値は $$\sum_{x=1}^\infty x2^{-x} = 2,$$ 分散は $$\sum_{x=1}^{+\infty} (x-2)^2 2^{-x} = 2$$ となります。
小課題
すべてのテストケースにおいて、以下が成り立ちます。
- $2 \le n \le 100$、$1 \le m \le n^2$
- $1 \le S, T \le n$、$S \neq T$
- $1 \le x, y \le n$、$0 \le o \le 1$
- どの頂点から出発しても $T$ に到達する経路が存在する
小課題 1 (4点): $o = 0$
小課題 2 (24点): $o = 1$
小課題 3 (8点): $m = n-1$、グラフにおいて $S$ のみが入次数 $0$ であり、$T$ のみが出次数 $0$ である
小課題 4 (20点): 与えられたグラフに閉路が存在しない
小課題 5 (44点): 特殊な制限なし
採点方法
各テストケースにおいて、それぞれの問いに正しく回答するごとに、そのテストケースの配点の $50\%$ を獲得できます。各小課題の得点は、その小課題に含まれるすべてのテストケースの得点の最小値となります。
注記
値域が自然数集合である確率変数 $X$ について、$X = x$ となる確率を $P_x$ とすると、$X$ の期待値は $$\mathbb{E}[X] = \sum_{x = 0}^{+\infty} x P_x,$$ $X$ の分散は $$\text{Var}[X] = \mathbb{E}[(X - \mathbb{E}[X])^2] = \sum_{x=0}^{+\infty} (x-\mathbb{E}[X])^2 P_x$$ と定義されます。