問題文

N 頂点 M 辺の有向グラフ G および 正の整数 K が与えられます。
G の頂点および辺には頂点 1, 頂点 2, ..., 頂点 N および 辺 1, 辺 2, ..., 辺 M と番号づけられており、辺 i (1 \leq i \leq M) は 頂点 u_i から 頂点 v_i へ向かう辺で、パラメータ b_i が付加されています。 b_i は 0 または 1 です。

有向グラフ G について、以下の 3 つのことが保証されます。

• G は多重辺を持たない。
• G はサイクルを持たない。
• 各頂点は頂点 1 から辺をたどることで到達でき、頂点 1 からの最短経路の長さと最長経路の長さは一致し、それは K 以下である。

2 つの駒を使って、2 人のプレイヤーがゲームを行います。

• 最初、各プレイヤーは自分の駒を頂点 1 に置く。
• プレイヤーは自分のターンになったら以下の操作のどちらかを行う。
  • 移動 : 自分の駒をちょうど 1 回移動させる。自分の駒が頂点 i にあるとき、頂点 i から頂点 j へ向かう辺があるような頂点 j へのみ移動させることができる。ただし、自分の駒が頂点 1 にあるときは、移動できる頂点から等確率でランダムに 1 つ選んで移動させなければならない。また、先手のプレイヤーは全ての辺を、後手のプレイヤーは b_i=0 である辺のみを使用することができる。
  • 敗北宣言 : 自分の負け、相手の勝ちとしてゲームを終了とする。
• 先手のプレイヤーから交互にターンを繰り返し、敗北宣言が行われないならば、後手のプレイヤーが 移動を K 回行った直後の時点でゲームを終了とする。その時点で 2 つの駒が同じ頂点にあるなら後手の勝ち、異なる頂点にあるなら先手の勝ちとなる。

各プレイヤーは自分の勝ちを目指して最適な戦略を取ります。
先手のプレイヤーが勝つ確率を \bmod 998244353 で求めてください。

制約

• 2 \leq N \leq 4{,}000
• 1 \leq M \leq 2 \times 10^{6}
• 1 \leq K \leq 4{,}000
• 1 \leq u_i, v_i \leq N
• b_i \in \{0, 1\}
• G は多重辺を持たない。
• G はサイクルを持たない。
• 各頂点は頂点 1 から辺をたどることで到達でき、頂点 1 からの最短経路の長さと最長経路の長さは一致し、それは K 以下である。
• 入力はすべて整数

小課題

1. (1 点) N\leq100, M\leq1000
2. (99 点) 追加の制約はない

入力例 1

5 6 2
1 2 0
1 3 0
2 4 0
2 5 0
3 4 0
3 5 1

出力例 1

499122177

各プレイヤーが駒を 1 回移動させた時点で、先手の駒が存在する頂点を i、後手の駒が存在する頂点を j としたときの組 (i, j) のうち、先手が勝つ組と後手が勝つ組はそれぞれ以下です。

• 先手が勝つ組 : (2, 3)、(3, 3)
• 後手が勝つ組 : (2, 2)、(3, 2)

この 4 つの組のうち、(3, 2) が選ばれたとき、以下のような進行が考えられます。

• まず頂点 1 に駒を置く。
• 先手が辺 2 を使用して自分の駒を頂点 3 へ移動させる。
• 後手が辺 1 を使用して自分の駒を頂点 2 へ移動させる。
• 先手が辺 6 を使用して自分の駒を頂点 5 へ移動させる。
• 後手が辺 4 を使用して自分の駒を頂点 5 へ移動させる。
• 後手が駒を 2 回動かしたのでゲームを終了とする。2 つの駒が頂点 5 に存在するため後手の勝ち

他にもゲームの進行は考えられますが、(3, 2) が選ばれた場合、先手がどのような戦略を取っても後手が勝つことができます。

なお、先手が勝つ確率は \frac{1}{2} と求めることができ、これを \bmod 998244353 で表現すると 499122177 となります。

このテストケースは小課題 1 の制約を満たします。

入力例 2

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

出力例 2

249561089

各プレイヤーが駒を 1 回移動させた時点で、先手の駒が存在する頂点を i、後手の駒が存在する頂点を j としたときの組 (i, j) のうち、先手が勝つ組と後手が勝つ組はそれぞれ以下です。

• 先手が勝つ組 : (2, 3)、(3, 2)、(3, 3)
• 後手が勝つ組 : (2, 2)

この 4 つの組のうち、(3, 2) が選ばれたとき、以下のような進行が考えられます。

• まず頂点 1 に駒を置く。
• 先手が辺 2 を使用して自分の駒を頂点 3 へ移動させる。
• 後手が辺 1 を使用して自分の駒を頂点 2 へ移動させる。
• 先手が辺 5 を使用して自分の駒を頂点 5 へ移動させる。
• 後手が辺 3 を使用して自分の駒を頂点 4 へ移動させる。
• 後手が駒を 2 回動かしたのでゲームを終了とする。2 つの駒が異なる頂点に存在するため先手の勝ち

他にもゲームの進行は考えられますが、(3, 2) が選ばれた場合、後手がどのような戦略を取っても先手が勝つことができます。

なお、先手が勝つ確率は \frac{3}{4} と求めることができ、これを \bmod 998244353 で表現すると 249561089 となります。

このテストケースは小課題 1 の制約を満たします。

入力例 3

2 1 1
1 2 1

出力例 3

1

後手は 移動を 1 回も行うことなく敗北宣言しなければなりません。

このテストケースは小課題 1 の制約を満たします。

入力例 4

16 21 3
1 2 0
1 3 0
2 4 0
2 5 0
3 6 0
3 7 0
4 8 0
4 9 0
5 10 0
5 11 0
1 12 1
1 13 1
12 14 1
12 15 1
13 6 1
13 7 1
14 8 1
14 9 1
15 10 1
15 11 1
1 16 0

出力例 4

199648871

このテストケースは小課題 1 の制約を満たします。