Piku arranges $$$N$$$ ants evenly around a perfect circle, placing one ant at each position.
When he flips a magical switch, each ant instantly moves, choosing independently to step either to its nearest left or nearest right neighbor. All ants move simultaneously at the same time, and each movement is equally likely. Every ant will move only once .
He will flip the magical switch exactly once .
A collision occurs if two ants move toward each other from adjacent positions.
Piku wants to know what is the probability that at least two ants collide? Can you help him?
The first line contains a single integer $$$T (1 \leq T \leq 10^5)$$$, the number of test cases.
The only line of each test case contains a single integer $$$N (3 \leq N \leq 10^7)$$$, the number of ants.
Print the probability where at least two ants collide.
Let this probability be represented as an irreducible fraction $$$\frac{x}{y}$$$. You have to print $$$x⋅y^{−1}$$$ mod $$$10^9+7$$$, where $$$y^{−1}$$$ is the inverse element of $$$y$$$ modulo $$$10^9+7$$$ (such integer that $$$y⋅y^{−1}$$$ has remainder $$$1$$$ modulo $$$10^9+7$$$ ).
1 3
750000006
