正の整数 $N, M, S$ が与えられます。

長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ に対して条件を以下のように定めます。

条件

• どの連続する $M$ 項の和も $S$ に等しい。より厳密には、すべての $1 \le i \le N - M + 1$ について、$\displaystyle \sum_{j=i}^{i +M - 1}{A_j} = S$ を満たす。
• すべての $1 \le i \le N$ について、$A_i \ge 1$
• すべての $1 \le i \le N$ について、$A_i$ は整数

条件をすべて満たす長さ $N$ の数列がいくつあるかを $998244353$ で割ったあまりを求めてください。

Hard (50点)

• $1 \le N, S \le 10^9$
• $1 \le M \le \min(N, 10^5)$
• 入力はすべて整数

Easy (100点)

• Hardの制約に以下の制約を追加
• $1 \le N, M, S \le 100$

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

答えを出力せよ。