Manny and Luke are playing a game. As Manny believes himself to be superior than Luke, he challenges Luke by giving a number n and asks Luke to tell the number of solutions of the following equation.
a+b+c=n
such that ,
a>=0 , b>=0 , c>=0 and
(a & b & c)>0
where '&' refers to Bitwise And operator.
Since Luke finds Maths very boring but wants to prove Manny wrong, he asks for your help.
Since, the answer can be too large, you need to calculate it Modulo 1000000007.
Input:
First line of the input contains an integer T denoting the number of test cases.
The following T lines contains the integer n.
Output:
Print one integer, denoting the number of solutions of the given equation when order does matter.
Constraints:
T <= 10^3
0 <= n <= 10^18
Problem Setter: Tanya
In the first test case , 10 can be written as sum of three numbers in many ways out of which only (a=2 , b = 2 , c = 6 ) , ( a=2 , b = 6 , c = 2 ) and (a = 6, b = 2 , c = 2) , follows all the conditions given i.e. (a & b & c) > 0.
