mehta-and-mathematical-equation

Background:
Verma was very afraid of his maths test to be held at school, the next day. So, he dreamt of one of the hardest questions that is likely to be asked in the exam.
He calls his friend Mehta, who is already good at maths.
So, he asks Mehta to solve the following task.

Task:
You will given a number N.
F(N) is defined as number of solutions of the following equation.
  such that,1.   2. (x & y & z) > 0,  where '&' refers to Bitwise And operator.
Since, the answer can be too large, you need to calculate F(N) Modulo 1000000007.

Input:
First Line of the input contains number of test cases T.
Next T Lines of the input contains a single integer N as described above.

Output:
Print F(N) for each given N in a separate line.

Constraints:
T  ≤ 10^3
0 ≤ N ≤ 10^18

SAMPLE INPUT
5
10 
123
345
567
231

SAMPLE OUTPUT
3
4105
30142
111295
17551

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming

Bit manipulation


Solutions: