H. A Certain Scientific Tree Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Misaka has come up with a very good problem for this contest. Unfortunately, that problem already exists (on at least 3 different online judges!) so she has to add a creative twist to it!

Consider a full binary tree of depth $$$d$$$. Remember a full binary tree with depth $$$d$$$ has $$$2^d - 1$$$ nodes and there is an edge from each node $$$u$$$ $$$(2 \leq u \leq 2^d -1)$$$ to its parent $$$\left \lfloor \frac{u}{2} \right \rfloor$$$. Misaka asks you to find the sum of distances between every pair of nodes on the tree.

Formally if $$$n = 2^d - 1$$$ ($$$n = \#$$$ nodes on the tree), compute:

$$$$$$S = \displaystyle\sum_{i = 1}^{n} \sum_{j = 1}^{n} dist(i, j)$$$$$$

where $$$dist(i, j)$$$ is the minimum number of edges on any path between node $$$i$$$ to node $$$j$$$.

Input

The first line will contain one integer $$$T$$$ denoting the number of multitests $$$(1 \leq T \leq 5)$$$.

The first line of each test will contain one integer $$$d$$$ the depth of the binary tree $$$(1 \leq d \leq 10^5)$$$.

 —

Testcases in subtasks are numbered $$$1 - 20$$$ with samples skipped.

Testcases $$$1 - 4$$$ satisfy $$$i$$$'th multitest of the $$$j$$$'th testcase has $$$d = (j-1)\cdot5 + i$$$. For instance testcase $$$2$$$ will consist of $$$d = [6, 7, 8, 9, 10]$$$ across the $$$5$$$ multitests.

Testcases $$$5 - 8$$$ satisfy $$$1 \leq d \leq 10^2$$$.

Testcases $$$9 - 12$$$ satisfy $$$1 \leq d \leq 10^3$$$.

The remaining testcases do not satisfy any additional constraints.

Output

Output one integer $$$S$$$ per testcase denoting the sum of distances across all pairs of nodes on the tree. Since this number may be very large, please find it modulo $$$10^9 + 7$$$.

Example
Input
5
1
2
3
20
3366
Output
0
8
96
443317199
359215119
Note

In the first sample, the tree only has $$$1$$$ node. As $$$dist(1, 1) = 0$$$, the answer would just be $$$0$$$.

In the second sample, there are $$$3$$$ nodes on a full binary tree with depth $$$2$$$. There are edges $$$1 - 2$$$ and $$$1 - 3$$$.

$$$dist(1, 1) = 0$$$

$$$dist(1, 2) = 1$$$

$$$dist(1, 3) = 1$$$

$$$dist(2, 1) = 1$$$

$$$dist(2, 2) = 0$$$

$$$dist(2, 3) = 2$$$

$$$dist(3, 1) = 1$$$

$$$dist(3, 2) = 2$$$

$$$dist(3, 3) = 0$$$

$$$0 + 1 + 1 + 1 + 0 + 2 + 1 + 2 + 0 = 8$$$ so $$$8$$$ is the answer.

 —

Idea: 3366

Preparation: 3366

Occurrences: Novice 9, Advanced 4