問題文
1 以上の整数 n が与えられます。
次のように定義される数列 {an} があります。
- 初項は a1 であり,a1=a2=1 である。また,ai+2=ai+1+ai(i≥1) を満たす。
次の式で求まる値を 998244353 で割った余りを出力してください。
j=1∑naj2
制約
- 1≤n≤1018
- n は整数である
入力
1 行に n が与えられます。
出力
答えを 1 行に出力してください。改行も忘れないこと。
入力例 1
出力例 1
入力例 2
出力例 2
998244353 で割った余りを出力することに注意してください。