It's 2080. There is a CROWDITORIUM in MANIT Bhopal, the first of its kind.
Generally, Auditoriums are supposed to have the same number of seats in each row, but this one is different.
E.g.
One day, Akash, who is very fond of Mathematics, volunteered for a task.
As he got bored by his task, his love for mathematics made him create a problem.
As Aakash went to play Golf with his friend Mayank, he left the problem unsolved. Can you solve this problem and get a step closer to winning Codathon?
INPUT
The First Line of Input consists of a single positive integer T denoting the number of test cases.
Each of next T lines consists of a single positive integer N denoting the number of columns in the auditorium.
OUTPUT
For each of the test case output a single positive integer denoting Sfinal. As the answer could be large, you have to precisely print Sfinal%1000000007
CONSTRAINTS
1 ≤ T ≤ 106
1 ≤ N ≤ 1018
NOTE: Use Fast I/O technique for large Input.
In case 1, the auditorium has 1 and only seat in a single column and since that is reserved for ladies there is only one way.
L
Sfinal = S1 = 1
In case 2, the auditorium has 1 seat in one column and 2 seats in the second column, the front row of each column is reserved for ladies
There is only one way to fill column 1
L
S1=1
There are two ways to fill column 2
L
G
or
L
L
S2=3
Hence Sfinal=4