You are given a set S = {1, 2, 3 ... n}. Your task is simple. You have to calculate the number of ways of selecting non empty subsets A and B such that A is not a subset of B and B is not a subset of A. Since answer can be large output the result mod 10⁹ + 7.

Input

First line of input contains single integer t denoting number of test cases.

Next t lines contain a single integer n.

Output

For each test case output answer to problem by taking mod with 10⁹ + 7.

Constraints

1 ≤ t ≤ 100000

1 ≤ n ≤ 1000000

Example

INPUT:
2
4
8
OUTPUT:
110
52670