Sum of Squares of Fibonacci Sequence

2 secs 1024 MB
OxOmiso

問題文


以上の整数 が与えられます。
次のように定義される数列 があります。

  • 初項は であり, である。また, を満たす。

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

制約


  • は整数である

入力


行に が与えられます。

出力


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

入力例


2

出力例


2

入力例


100

出力例


276827820

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

提出


Go (1.14)