Assi, Bakku and ACM

3.6

16 votes
Very-Easy
Problem

After so many days of request, Assi The great finally agreed to team up with Bakku for ACM ICPC. Now they're discussing their strategy for ICPC.

Assi : "Bhai Logic sochna mushkil hota hai, implementation to easy hai. Isliye logic mein sochunga, implement tu karna." ( Logic is hard to think, implementation is very easy. So, I'll think logic and you'll do implementation).

To this, Bakku is very surprised as he knew sometimes implementation can become very frustrating. But he didn't dare to object Assi on this, as he is Assi - The Great.

So they started solving problems. First problem is : Given a full binary tree with N nodes numbered as 1, 2, 3, ... , N and rooted at 1. There is an edge from i to 2*i with weight 2*i and from i to 2*i+1 with weight 2*i+1. Find sum of all pair path length of nodes.

Sample tree with N = 7.

enter image description here

Even though thinking logic is Assi's task but he is now busy in Idockady. So, help Bakku to solve this question.

Input

The first line of the input contains a single integer T (1 ≤ T≤ 100) — the number of test cases.

Each test case contains single integer N ( 1 <= N <= 100000 )

Output

Print T lines, for each test case print desired output modulo 1000000007;

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

Tree is :

enter image description here

Path length for each pair

(1,2) : 2

(1,3) : 3

(2,3) : 2+3

Total Sum : 2 + 3 + 5 = 10

Editor Image

?