No.718 行列のできるフィボナッチ数列道場 (1)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 67
作問者 : hirakich1048576hirakich1048576 / テスター : ixmelixmel
3 ProblemId : 1240 / 出題時の順位表

問題文

数列 $ F_i $ を以下のように定義する.
$ \begin{cases} F_0 = 0 \\ F_1 = 1 \\ F_{i+2} = F_{i+1} + F_i \end{cases} $
与えられる整数 $ N $ に対して, $ \large{ \sum_{i=1}^{n} F_i^2 = \overbrace{F_1^2 + F_2^2 + \cdots + F_n^2}^{n} } $ を計算せよ.
答えは非常に大きな数になることがあるので,$ 1000000007 $で割った余りを答えよ.

入力

$ N $

$ 1 \leqq N \leqq 10^{10} $

出力

$ \large{ \sum_{i=1}^{n} F_i^2 = \overbrace{F_1^2 + F_2^2 + \cdots + F_n^2}^{n} } $ の値を$ 1000000007 $で割った余りを1行に出力せよ.

サンプル

サンプル1
入力
8
出力
714

$ 1^2 + 1^2 + 2^2 + 3^2 + 5^2 + 8^2 + 13^2 + 21^2 $の値$ 714 $が答えです.

サンプル2
入力
33550336
出力
381853718

サンプル3
入力
10000000000
出力
128493982

入力$ N $は32bit整数に収まらないことがあります.

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。