SOLVE

LATER

Modern Game

/

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

Explanation

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.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...