Link to Russian translation of problem

There are N ants staying at the vertices of the N-regular polygon (one ant at one vertex). At some moment of time all the ants choose one of the edges their vertex is adjacent to and start walking along this edge. If two ants meet at some point of the edge they die. Please find the probability that all the ants will survive.

Input
The first line contains one integer T - number of test cases. The following T lines contain one integer each - N.

Output
We can consider answer as a fraction P / Q. For each test case output P * Q^-1 modulo 10⁹ + 7.

Constraints

T <= 1000
3 <= N <= 10¹¹