To qualify for a job interview Px has to solve Easy Function. Being a newbie Px needs your help to qualify for the job. Help him to solve the following Easy Function.
F(n) is a function defined by the recursive relation :
F(n) = F(n-1) - F(n-2) + n for n >= 2
F(0)=1, F(1)=1
Let S(n) be the function defined as :
S(n)=∑ni=0F(i) Your task is to calculate the value of S(n) for the given value of n for every test case.
As your answer can be very large print the value of S(n) modulo 1,000,000,007.
CONSTRAINTS :
1 ≤ T ≤ 100
1 ≤ N ≤ 10^18
INPUT :
First Line contains T i.e. number of the test case.
Each of the next T lines contains an integer N.
OUTPUT :
For each test case print the value of S(N) modulo 1,000,000,007
For Test Case 1 :
N=2
F(0) = 1, F(1) = 1
F(2) = F(1) - F(0) + 2
F(2) = 1 - 1 + 2
F(2) = 2
S(2) = F(0) + F(1) + F(2)
S(2) = 1 + 1 + 2
S(2) = 4
