Let's define a 10-string as a string that contains only characters '1' and '0', starts with '1' and ends with '0'. For example, "10101010", "100" or "1010" are 10-strings, while "011", "11120" or "10101" are not.

A subsequence of any 10-string is called humongous if it is of the form "1010...10" ("10" concatenated an arbitrary number of times).

For example, the 10-string "110" contains exactly 2 humongous subsequences and "1010" contains exactly 4 humongous subsequences (formed using indices {1, 2}, {3, 4}, {1, 4}, {1, 2, 3, 4}).

You should process some really humongous queries. Each query is as follows:

1) You're given length of string S.

2) You can convert S into another string U by flipping a number of characters (possibly zero; a flip means changing a '1' to '0' or '0' to '1') of S.

3) Let us denote the number of humongous subsequences of U as X.

4) The answer to the query is the maximum X you can get.

For each query, compute the maximum number of humongous subsequences you can get.

As the answer can be very large, output it modulo 1000000007 ((10^9)+7).

See Sample test-case for more understanding.

Input format:

The first line of the input contains a single integer T denoting the number of test cases.

Each of the next T lines contains a single integer n denoting the length of string S.

Output format:

For each query, output the required answer on new line.

Constraints:

1 <= Q <= 10^6

2 <= n <= 10^7