方向音痴

※作問初心者なので、細かいミスがあったらごめんなさい。

問題文

Loop 王国は $N$ 個の街と $M$ 本の道路からなり、街には $1$ から $N$ までの番号が付いています。
$i$ $(1 \leq i \leq M)$ 番目の道路は街 $A_i$ と街 $B_i$ を双方向に結んでおり、通るのに $C_i$ 分かかります。

方向音痴の Alice さんは街 $N$ に辿り着くまで、街から出ている全ての道路から一様ランダムに $1$ 本選び、その道路を通って別の街に移動する行動を繰り返します。

街 $N$ に辿り着いた後はずっと街 $N$ に滞在します。 Alice さんが道路を選ぶのにかかる時間は $0$ 分です。

方向音痴の Alice さんは現在街 $1$ にいます。 $T$ 分以内に街 $N$ に辿り着く確率を $\mathrm{mod} \ 998244353$ で求めてください。

確率 $\mathrm{mod} \ 998244353$ の定義

この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 $\frac{y}{x}​$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。
このとき $xz \equiv y \ (\mathrm{mod} \ 998244353)$ を満たすような $0$ 以上 $998244352$ 以下の整数 $z$ が一意に定まります。この $z$ を答えてください。

制約

• $2 \leq N \leq 50$
• $1 \leq M \leq \min(\frac{N(N-1)}{2}, 500)$
• $1 \leq A_i < B_i \leq N$
• $(A_i, B_i)$ は相異なる
• $1 \leq C_i \leq 10^9$
• $1 \leq T \leq 1000$
• 入力は全て整数である

入力

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

出力

答えを出力してください。最後に改行してください。

サンプル

入出力例 1

3 3 3
1 2 2
1 3 1
2 3 1

249561089

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

1. 街 $1$ から道路 $1$ を通って、街 $2$ に $2$ 分かけて行く。
2. 街 $2$ から道路 $2$ を通って、街 $3$ に $1$ 分かけて行く。

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

この問題におけるLoop王国の地図はこのようになります。

入出力例 2

2 1 1000
1 2 1

1

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

入出力例 3

6 10 100
1 3 12
1 4 3
2 3 4
2 4 32
2 5 16
2 6 9999
3 4 10
3 5 9999
4 6 64
5 6 20

218482382