Key Set

soda has a set S with n integers {1, 2, ... , n}. A set is called key set if the sum of integers in the set is an even number. He wants to know how many nonempty subsets of S are key set.

There are multiple test cases. The first line of input contains an integer T (1 <= T <= 10^5), indicating the number of test cases. For each test case:

The first line contains an integer n (1 <= n <= 10^9), the number of integers in the set.

For each test case, output the number of key sets modulo 1000000007.