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.
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;
Tree is :
Path length for each pair
(1,2) : 2
(1,3) : 3
(2,3) : 2+3
Total Sum : 2 + 3 + 5 = 10