問題文

和太鼓ゲームにお金を使いすぎたので、スーパーマーケットのカート回収のバイトでお金を稼ぎにしました。
スーパーマーケットから一方向に伸びる半直線状の通路にカート置き場が$N$個あり、カート置き場$i \ (1 \leq i \leq N)\$はスーパーマーケットから距離$i$の位置に設置されています。
カート置き場$i$には、カートが$Ai$台溜まっていることがわかっています。カートは$1$回で$K$台まで持つことが出来ます。
そこで、以下の作戦ですべてのカートを回収することにしました。
$1$.$K$台以上溜まっているカート置き場がある場合、そこから$1$つ選び、そのカート置き場に置かれているカートが$K$台未満になるまで、そのカート置き場から$K$台ずつ運ぶ。
$2$.すべてのカート置き場が$K$台未満になったら、カートが置かれているカート置き場の中でスーパーマーケットから一番遠いカート置き場に行き、戻る途中で$K$台になるまで貪欲に集めて運ぶ。つまり、今置かれているカートのうち、スーパーマーケットからの距離が遠いものから$K$台運ぶ。
この作戦を実行し、カートをすべてスーパーマーケットに回収したときの移動距離を$998244353$で割った余りを求めてください。なお、回収途中にカートは増えないものとし、回収する際に、カートを回収する予定のあるカート置き場に最短距離で向かうものとします。

入力

$N\ A\ K$

・$1 \leq N \leq 10^{16}$
・$1 \leq A < K$
・$2 \leq K \leq 10^5$
・$N,A,K$はすべて整数

出力

カートをすべて回収したときの移動距離を$998244353$で割った余りを出力してください。

サンプル

3 5 6

26

1 1 10

2