Sum of Squares of Fibonacci Sequence

2 secs 1024 MB
OxOmiso's icon OxOmiso

問題文

11 以上の整数 nn が与えられます。
次のように定義される数列 {an}\{a_n\} があります。

  • 初項は a1a_1 であり,a1=a2=1a_1 = a_2 = 1 である。また,ai+2=ai+1+ai  (i1)a_{i+2} = a_{i+1}+a_i \; (i\geq1) を満たす。

次の式で求まる値を 998244353998244353 で割った余りを出力してください。

j=1naj2\sum_{j=1}^{n}{{a_j}^2}

制約

  • 1n10181 \leq n \leq 10^{18}
  • nn は整数である

入力

11 行に nn が与えられます。

出力

答えを 11 行に出力してください。改行も忘れないこと。

入力例 11

2

出力例 11

2

入力例 22

100

出力例 22

276827820

998244353998244353 で割った余りを出力することに注意してください。

提出


Go (1.21)