方向音痴

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

Loop 王国は 個の街と 本の道路からなり、街には から までの番号が付いています。
番目の道路は街 と街 を双方向に結んでおり、通るのに 分かかります。

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

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

方向音痴の Alice さんは現在街 にいます。 分以内に街 に辿り着く確率を で求めてください。

この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 で表したときに が で割り切れないことが保証されます。
このとき を満たすような 以上 以下の整数 が一意に定まります。この を答えてください。

• は相異なる
• 入力は全て整数である

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

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

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

249561089

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

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

Aliceさんは の確率で時間内に街 に辿り着くことができます。よって、 を満たすため、答えとして を出力します。

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

2 1 1000
1 2 1

1

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

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