D - Poor Sense of Direction

2 secs 1024 MB
loop0919's icon loop0919

問題

Loop 王国は NN 個の街と MM 本の道路からなり、街には 11 から NN までの番号が付いています。
ii 番目 (1iM)(1 \leq i \leq M) の道路は街 uiu_i と街 viv_i を双方向に結んでおり、通るのに tit_i 分かかります。

Alice さんは街 NN に辿り着くまで、街から出ている全ての道路から一様ランダムに 11 本選び、その道路を通って別の街に移動する行動を繰り返します。
Alice さんは、道を通っているときに立ち止まったり引き返したりすることはなく、道路を選ぶときにかかる時間は無視できます。
そして、街 NN に辿り着いた後はずっと街 NN に滞在します。

Alice さんは現在街 11 にいます。 TT 分以内に街 NN に辿り着く確率を mod 998244353\mathrm{mod} \ 998244353 で求めてください。

確率 mod 998244353\mathrm{mod} \ 998244353 とは

この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 yx\frac{y}{x}​ で表したときに xx998244353998244353 で割り切れないことが保証されます。

このとき xzy (mod 998244353)xz \equiv y \ (\mathrm{mod} \ 998244353) を満たすような 00 以上 998244352998244352 以下の整数 zz が一意に定まります。この zz を答えてください。

制約

  • 2N10002 \leq N \leq 1000
  • 1M10001 \leq M \leq 1000
  • 1T20001 \leq T \leq 2000
  • 1ui<viN1 \leq u_i < v_i \leq N
  • ij(ui,vi)(uj,vj)i \ne j \Longrightarrow (u_i, v_i) \ne (u_j, v_j)
  • 1tiT1 \leq t_i \leq T
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

NNMMTT
u1u_1v1v_1t1t_1
\vdots
uMu_MvMv_MtMt_M

出力

答えを出力せよ。

サンプル 1

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

例えば、 Alice さんは以下の行動で街 3333 分以内で辿り着きます。

  1. 11 から道路 11 を通って、街 2222 分かけて行く。
  2. 22 から道路 22 を通って、街 3311 分かけて行く。

Aliceさんは 34\frac{3}{4} の確率で時間内に街 33 に辿り着くことができます。よって、 4×2495610893 (mod 998244353)4 \times 249561089 \equiv 3 \ (\mathrm{mod} \ 998244353) を満たすため、答えとして 249561089249561089 を出力します。

サンプル 2

入力2
2 1 1000
1 2 1
出力2
1

絶対に時間内に辿り着けます。

サンプル 3

入力3
6 10 100
1 3 12
1 4 3
2 3 4
2 4 32
2 5 16
2 6 100
3 4 10
3 5 100
4 6 64
5 6 20
出力3
218482382

Submit


Go (1.21)