H. Hiro's Hero
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Hiro just entered fifth grade. His best friend, Liam, is his closest competitor in the class. They both perform well in their studies, and they both admire the same girl, Selin. One day, after school, they decided to find out who is a better match with Selin. Selin is a smart girl and she likes people who are also sharp-minded. She is recently struggling with a math problem, and she might be impressed if Hiro could solve it. The problem is stated as follows.

The alternating sum of a non-empty set is defined as follows. First, arrange the numbers in the set in decreasing order. Then, beginning with the largest number, add and subtract numbers alternatingly. For instance, the alternating sum of $$$\{3, 1, 7, 5, 9\}$$$ is $$$9 - 7 + 5 - 3 + 1 = 5$$$ and for $$$\{7\}$$$, it's simply $$$7$$$. Given a set of numbers $$$S = \{1, 2, 3, 4, 5, 6, 7\}$$$, what is the sum of the alternating sums of all the non-empty subsets of $$$S$$$?

You, as a student from NTU, seem to be smart. Your mission is to solve the sum of the alternating sums of all the non-empty subsets of the given sets. Be Hiro's Hero and win Selin over!

Input

The first line contains one integer $$$t\,(1 \leq t \leq 10^5)$$$, the number of test cases. Then $$$t$$$ test cases follow.

In the following $$$t$$$ lines, each line contains an integer $$$n\,(1 \leq n \leq 10^5)$$$, which is the cardinality (number of elements) of the given set $$$S$$$. To make the problem simpler, $$$S = \{1, 2, 3, \ldots, n\}$$$.

Output

For each test case, output the answer (i.e. the sum of the alternating sums of all the non-empty subsets of the given set) modulo $$$1000000007$$$ in a new line.

Examples
Input
1
3
Output
12
Input
2
3
7
Output
12
448
Input
1
100000
Output
175787298
Note

In the first test case, all the non-empty subsets of $$$\{1, 2, 3\}$$$ are $$$\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}$$$ and $$$\{1, 2, 3\}$$$.

  • The alternating sum of $$$\{1\}$$$ is $$$1$$$.
  • The alternating sum of $$$\{2\}$$$ is $$$2$$$.
  • The alternating sum of $$$\{3\}$$$ is $$$3$$$.
  • The alternating sum of $$$\{1, 2\}$$$ is $$$2 - 1 = 1$$$.
  • The alternating sum of $$$\{1, 3\}$$$ is $$$3 - 1 = 2$$$.
  • The alternating sum of $$$\{2, 3\}$$$ is $$$3 - 2 = 1$$$.
  • The alternating sum of $$$\{1, 2, 3\}$$$ is $$$3 - 2 + 1 = 2$$$.
So, the sum of all alternating sums is $$$1 + 2 + 3 + 1 + 2 + 1 + 2 = 12$$$.