Problem E
Eindahraðall

A particle accelerator is being built in Iceland. The accelerator is $N$ Planck lengths in length and is circular. An experiment is planned where two particles should collide. At the start, an electron is placed inside the circular accelerator and the magnets then start to accelerate it. It always moves an integer number of Planck lengths forward. As it is accelerating, it will at each step move further than in the last. In the first step, it moves $1$ unit forward with probability half, $2$ units with probability a quarter, and so forth. Going forward if it moved $k$ units in the previous step, it will move $k + 1$ units forward with probability half this time, $k + 2$ with probability a quarter, and so forth. When the particle moves $\geq N$ units in a single step the magnets cannot keep it contained anymore. Thus, we want the collision to happen at this exact moment, and for this the particle needs to be where it started. What is the probability of this occurring?

For example if $N = 7$ it could move two units forward, then three and finally six before it needs to collide. In this example it does not end up where it started, but many other sets of moves are possible. To better understand how often this repelling effect comes into play, we are interested in the probability that the particle is at the origin when the experiment ends. If the particle is at the origin it is equally likely to go left or right. If the particle moves $k$ steps it is equally likely to take $k + 1$ steps next or to take more than $k + 1$ steps next. Similarly, it is equally likely to take $k + 2$ steps and to take more than $k + 2$ steps, so it half of the time it takes $k + 1$ steps, a quarter of the time it takes $k + 2$ steps, and so forth.

Input

The first line of the input contains a single integer $1 \leq t \leq 100$, the number of test cases. Then $t$ lines follow, each representing a test case with one integer $N$, where $1 \leq N \leq 10^{18}$.

Output

For each $N$ in the input, print the probability for that $N$ as explained above on its own line. The probability can be written as a reduced fraction $p/q$. Since these numbers could be very large, you should instead print $pq^{-1}$ modulo $1\, 000\, 000\, 007$, where $q^{-1}$ is the multiplicative inverse of $q$ modulo $1\, 000\, 000\, 007$.

For example, if $p=2$ and $q=4$, then we find the integer $q^{-1}$ such that $q \cdot q^{-1} \equiv 1 \pmod{1\, 000\, 000\, 007}$. Since $4 \cdot 250\, 000\, 002 = 1\, 000\, 000\, 008$ and $1\, 000\, 000\, 008 \equiv 1 \pmod{1\, 000\, 000\, 007}$, we can compute $pq^{-1} \equiv 2 \cdot 250\, 000\, 002 \equiv 500\, 000\, 004 \pmod{1\, 000\, 000\, 007}$.

5
1
2
3
4
100

1
500000004
500000004
250000002
263762378