It's again Jawa's birthday today. He has toffees with sweetness {1,2,3, . . . . . . ., n}. He wants to distribute these toffees to his two best friends Aneesh and Ashish. First he selects some subset A of these toffees and gives them to Aneesh. Now, he selects another subset B such that A is not a subset of B and B is not a subset of A and gives it to Ashish.

You have to help Jawa to decide what are the total number of ways in which he can distribute toffees to Aneesh and Ashish. Since answer can be large output the result mod 10^9+7.

[Input]
First line of input contains single integer t denoting number of test cases.
Next t lines contain a single integer n denoting maximum sweetness he have in toffees.

[Output]
For each test case output answer to problem by taking mod with 10^9 + 7.

[Constraints]
1<=t<=100000
1<=n<=1000000