問題一覧 > 通常問題

No.718 Fibonacci Sequence Dojo Where Matrices Line Up (1)

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 177
作問者 : hirakich1048576 / テスター : ixmel
お気に入りにしたユーザー ProblemId : 1240 / 自分の提出
問題文最終更新日: 2026-06-25 18:38:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 196 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。