注意

この問題は Have Another Go (Easy) の制約強化版です。Easy版との違いは、$6 \leq N\leq 10^{9}$ 、$1 \leq M \leq 10^{9}$ であることです。

ストーリー

必ずしもこの項を読む必要はない。

tfl君はとあるすごろくを $2$ 周しましたが...

tfl君「たった $2$ 周じゃコインが獲得できないぃぃ...」

highlighterはかせ「仕方ないのぉ。$M$ 周できるチャンスをやる。 $M$ は最大で $10^{9}$ にもなるぞい！これで文句ないじゃろ！（笑）」

tfl君「いやさすがに長すぎるだろ」

tfl君「...これ $M$ の下限 $1$ だから最悪さっきより悪化するのでは？」

highlighterはかせ「作問の都合じゃ、黙るがよい」

問題文

tfl君は次のようなゲームで遊んでいます。

• 変数 $X$ と空の配列 $Y$ を用意する。はじめ $X$ の値は $0$ に等しい。
• 以下の一連の操作を行う。
  • $X$ を $Y$ の末尾に付け加える。
  • $1$ 以上 $6$ 以下の整数が等確率で出るサイコロを振る。
  • $X$ にサイコロで出た目の数を加える。
  • $X \geq NM$ なら操作を終える。そうでないなら、またこの操作を繰り返す。

$i=1,2,\ldots k$ について、以下の問いに答えてください。

ただし、サイコロを振る操作は毎回独立です。

制約

• $6 \leq N \leq 10^{9}$
• $1\leq M\leq 10^{9}$
• $1 \leq k \leq 5000$
• $1 \leq C_{i} \lt N$
• 入力はすべて整数

入力

$N~~~M~~~k$
$C_{1} ~~~ C_{2} ~ \ldots ~ C_{k}$

出力

$k$ 行出力せよ。 $i$ 行目には、 $C_{i}$ に対する答えを $998244353$ で割った余りを出力せよ。

サンプル

100 100 5
1 2 3 4 5

138959755
683208998
780270567
968245045
696325744