No.718 Fibonacci Sequence Dojo Where Matrices Line Up (1)
タグ : / 解いたユーザー数 177
作問者 :
hirakich1048576
/ テスター :
ixmel
Problem Statement
Define the sequence $ F_i $ as follows.
$
\begin{cases}
F_0 = 0 \\
F_1 = 1 \\
F_{i+2} = F_{i+1} + F_i
\end{cases}
$
For the given integer $ N $, compute $ \large{ \sum_{i=1}^{n} F_i^2 = \overbrace{F_1^2 + F_2^2 + \cdots + F_n^2}^{n} } $.
Since the answer can be very large, output the remainder when it is divided by $ 1000000007 $.
Input
$ N $
$ 1 \leqq N \leqq 10^{10} $
Output
Output on one line the remainder when the value of $ \large{ \sum_{i=1}^{n} F_i^2 = \overbrace{F_1^2 + F_2^2 + \cdots + F_n^2}^{n} } $ is divided by $ 1000000007 $.
Sample
Sample 1
Input
8
Output
714
The answer is $ 714 $, the value of $ 1^2 + 1^2 + 2^2 + 3^2 + 5^2 + 8^2 + 13^2 + 21^2 $.
Sample 2
Input
33550336
Output
381853718
Sample 3
Input
10000000000
Output
128493982
The input $ N $ may not fit in a 32-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。