No.718 行列のできるフィボナッチ数列道場 (1)
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 169
作問者 :
hirakich1048576
/ テスター :
ixmel
タグ : / 解いたユーザー数 169
作問者 :
hirakich1048576
/ テスター :
ixmel
問題文最終更新日: 2018-07-27 22:49:59
問題文
数列 $ 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整数に収まらないことがあります．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。