407723: GYM102881 L The Expected Square

Ehab the baby likes playing games with $$$XOR$$$ (of course), so he will play the following game. He is given some number $$$n$$$. Then, he defines a number $$$x$$$ which is initially $$$0$$$. In each move, he thinks of a number $$$r$$$, where $$$r$$$ is a non-negative number strictly less than $$$2^n$$$ chosen uniformly at random, and changes $$$x$$$ to $$$x \oplus r$$$, where $$$\oplus$$$ denotes the bitwise $$$XOR$$$ operation. After making the first move, he stops when $$$x$$$ becomes $$$0$$$ again.

Baby Ehab was thinking of the expected value of the square of the number of moves that he will play. More formally, let $$$m$$$ be the number of moves he plays in a game, then Baby Ehab wants to know $$$E(m^2)$$$, Can you know it?

Let the answer be represented as $$$p/q$$$, then you are required to find the value of $$$p * q^{-1} \mod 10^9 + 7$$$.

The first line of input contains $$$t$$$, the number of test cases.

Each of the following $$$t$$$ lines contains one integer, $$$n$$$ ($$$1 \le n \le 10^9)$$$.

For each test case, output the required answer on a single line.

3
2
3
10

28
120
2096128