Modern Game
/
No tags
Problem
Editorial
Analytics

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

SAMPLE INPUT
3
10
123
345
SAMPLE OUTPUT
3
4105
30142
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

## This Problem was Asked in

Initializing Code Editor...