問題文
ある数列Aの先頭N項が与えられます。
Aは下の規則に則っています。
- Ai=Ai−1+Ai−2+...+Ai−N (i>N)
AK を 998244353 で割った余りを求めてください。
制約
- 2≤N<K≤2×105
- 1≤Ai≤109 (i≤N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
出力
AK を 998244353 で割った余りで出力してください。
サンプル
A は 1,1,2,3,5,8,13…となるので6項目の8を出力します。
A は 2,1,3,4,7,11,18…となるので6項目の11を出力します。
998244353で割った余りを出力してください。