小C得fib数列2

题号：NC207673
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小C在学习数列的时候发现了了一种比较有趣的数列:斐波那契数列。这种数列被定义为：f(n)=f(n-1)+f(n-2),f(1)=f(2)=1.他把这个优雅的数列分享给了小D，小D看了看说这个很简单，现在我有这样的一个数列：

$f(n+1)=f(n)+f(n-1)+(-1)^n+n \%5+ \lfloor log2(n) \rfloor$

其中 $\ f(1)=f(2)=1$

他问小C你知道这个数列怎么求嘛。小C一脸疑惑，向你请教。

首先第一行一个T，表示T个询问，然后接下来n行，每行一个n,表示输出该数列的第n项，由于数据比较大，只需要输出对(1e9+7)取模之后的结果即可。

询问的第n项答案。

示例1

复制

1
1

复制