3001. 不负AC不负卿

【问题描述】

TIM鍥剧墖20190622021350.jpg

出場選手のみなさん、こんにちわ、わたしは御坂美琴です、今日は一緒にがんばりましょうね。

不知不觉炮姐的ACM生涯已经快两年了,让我们再来看一看炮姐最喜欢以及当做信条的那段歌词。

世上定得两全法,不负AC不负卿。

愿风裁尽尘中沙,与君咫尺共天涯。

弱而不改凌云誓,穷且不坠青云志。

还记得当年你因为什么要下定决心无论风霜都要坚持ACM吗,今天就让我们回顾一下那道熟悉的斐波那契,找回曾经的你。


这是一个加强版的斐波那契递数列。

F(i) = 0                                                      i=0.

F(i) = 1                                                      i=1.

F(i) = F(i-1) + F(i-2) + i^3 + i^2 + i + 1       i>1.

求F(i)的值,由于这个值可能太大,请对109+7取模。

【输入形式】

第一行是一个整数T(1 ≤ T ≤ 1000),表示数据的个数。

以后每组数据一行,是一个整数n(1 ≤ n ≤ 1e18)。

【输出形式】

每个样例输出一行,一个整数,表示F(n) mod 1000000007。

【样例输入】

4

1

2

3

100


【样例输出】

1

16

57

558616258



难度等级: 0
总通过次数: 2
总提交次数: 77