お詫び(27'4/11 21:55追記)

コンテスト中に 00_sample_01.txt のケースに不備がありました。
解いてくれた皆さま、修正が遅れてしまい誠に申し訳ございませんでした。現在は修正済みです。

Story

🐇

「二兎追う者は一兎をも得ず」

やばい！！

あなたは新年度から忙し屋さんです。
巷では「急かされたら良い一年にならない」って言われているようですが、この始末です。

というのも、あなたが主催する「2027 Matcha's New Year Contest」というプログラミングコンテストに遅刻しそうなのです。
さすがに主催者であるあなたは、遅刻する訳にはいきません。

ひとまずあなたは深呼吸して、息を整わせます。
そして落ち着いて、この街の周辺地図を見ながら、どのように移動することがいいのか探ってみました。

あまり走りたくはないですが、間に合わせるためには背に腹は代えられません。
歩きにも走りにも自信はあるのでとりあえず時間には間に合わせる。そう思いながら行動し始めたようです。

開催できれば、次のコンテストももっと余裕があって元気よく開きたいものですね！
（心の声：頑張ります）

End.✨🏔

問題

ある世界では $N$ 個の街と $M$ 本の道で構成される構造をしています。
$i\ (1\le i\le M)$ 番目の道は街 $A_i$ から街 $B_i$ に一方向に繋がっており、これ以外につながっている道は存在しません。

あなたは、どういうわけかあなた主催のコンテストに遅刻しそうです。
なのであなたは、今いる街から道をたどって移動できる街を $1$ つ選び、次のいずれかの手段を使って移動することを繰り返し行うことにしました。

• 歩いて移動する。このとき $w$ 秒を要する。
• 走って移動する。このとき $r$ 秒を要する。

あなたは今、街 $1$ にいます。一方、コンテストが開催される街は 街 $f$ のようでした。

開催まで残り $T$ 秒となりました。
街 $1$ から街 $f$ までの移動に要した時間の合計が $T$ 秒以下となるような移動方法は、何通りあるか求めてください。
ただし答えは非常に大きくなる可能性があるので $998244353$ で割ったあまりを出力してください。

さらにこの問題では、$w,r,f$ がクエリ形式で $Q$ 回だけ与えられます。
$w=w_j, r=r_j, f=f_j\ (1\le j\le Q)$ とみなしたときの答えを順に求めてください。

入力

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

制約

• $2\le N\le 10^3$
• $1\le M\le 10N$
• $1\le T\le 10^{18}$
• $1\le A_i,B_i\le N$
• $1\le Q\le 2\times 10^4$
• $1\le r_j\lt w_j\le 10^{15}\ (1\le j\le Q)$
• $2\le f_j\le N\ (1\le j\le Q)$
• $A_i\ne B_i$
• $1\le i,j\le N$ において $i\ne j\Rightarrow (A_i,B_i)\ne (A_j,B_j)$
• ある街からそれぞれの街へ $2$ 回以上訪れるような移動方法が存在しない
• 任意の街について、街からつながる道は $10$ 本以下である
• 入力はすべて整数

出力

各クエリに対する答えを、次のような形式で改行区切りで出力せよ。ただし $j=K$ の場合の答えを $\text{answer}_K$ と表している。

入出力例

4 3 2
1 3
1 2
3 2
3
2 1 2
4 1 3
2 1 4

3
1
0

$1$ 個目のクエリについて説明します。与えられた街の構造において、街 $f_1(=2)$ に移動する方法は次のようになります。

• 街 $1\to 2$ と移動する
  • この移動で走ったとき、要する時間は $1$ 秒
  • この移動で歩いたとき、要する時間は $2$ 秒
• 街 $1\to 3\to 2$ と移動する
  • この移動で走ったとき、要する時間は $1+1=2$ 秒
  • $1\to 2$ の移動で走り、$2\to 3$ の移動で歩いたとき要する時間は $1+2=3$ 秒
  • $1\to 2$ の移動で歩き、$2\to 3$ の移動で走ったとき要する時間は $2+1=3$ 秒
  • この移動で歩いたとき、要する時間は $2+2=4$ 秒

以上の $6$ 通りの移動方法のうち、街 $1$ から街 $2$ にたどり着くのに要する時間が $T(=2)$ 秒以内であるような方法は $3$ 通りです。

また $3$ 個目のクエリについて、そもそも街 $1$ から街 $4$ に到達する移動手段は存在しません。