QCH与斐波那契数列 PLUS - 题目详情 - bzoj.org

ID: 370

传统题

1000ms

16MiB

难度: 8

上传者:

标签>

智力题

题目背景

HZX 觉得这道题目太简单了，于是他就加强了一下。

题目描述

众所周知，斐波那契数列 $f_i$ 的定义如下：

f_1=1,f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge3)

给出 $n$ ，定义 $s$ ：

s=\sum_{i=1}^nf_i^3

求 $s\bmod 10^9+7$ 的值。

输入格式

一行一个数 $n$ 。

输出格式

一行一个数表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

s=f_1^3+f_2^3+f_3^3=1^3+1^3+2^3=10

数据范围

对于 $30\%$ 的数据满足 $1\le n\le 10^6$ 。

对于 $100\%$ 的数据满足 $1\le n\le10^9$ 。