题号：NC15666
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
这是一个加强版的斐波那契数列。
给定递推式
%20%3D%20%5Cleft%5C%7B%20%5Cbegin%7Barray%7D%20%5C%5CF(i-1)%20%2B%20F(i-2)%20%2B%20i%5E3%20%2B%20i%5E2%20%2B%20i%20%2B%201%20%26%20i%3E1%20%5C%5C0%20%26%20i%20%3D%200%20%5C%5C1%20%26%20i%20%3D%201%5Cend%7Barray%7D%5Cright.)
求F(n)的值，由于这个值可能太大，请对109+7取模。
输入描述:
第一行是一个整数T(1 ≤ T ≤ 1000)，表示样例的个数。
以后每个样例一行，是一个整数n(1 ≤ n ≤ 1018)。
输出描述:
每个样例输出一行，一个整数，表示F(n) mod 1000000007。