Let us reverse the roles. You are a coronavirus and the honorable president of the coronavirus race. To put up a tough fight against the spirit that humans are showing to wipe out your race, you have decided to form teams of coronaviruses. Coronaviruses working in a team sacrifice themselves and combine all their strengths to become a single coronavirus to make it deadlier than ever such that it would break any immunity that comes in its way. They named this sacrifice – “Coronation” and the final coronavirus – “Megacorona”.

A team consists of 2N-1 coronaviruses (numbered 1 to 2N-1) such that each coronavirus has a strength equal to its number. Now, they start Coronating. The process involves N steps. In each step, any 3 coronaviruses (with strengths a, b, c) can sacrifice themselves to form a new coronavirus (with strength d). The new coronavirus joins the team and the process continues till exactly 1 coronavirus is left, which is the Megacorona.

d = a + b + c + ab + bc + ca + abc

Now the team of coronaviruses wonders what can be the maximum strength of the Megacorona assuming that the coronaviruses have coronated in optimal order.

Being the president, can you help them figure this out? Since the answer can be large, compute it modulo 10⁹+7.

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and the only line contains one integer – N.

Output:

For each test case, print a single line containing one integer – the maximum strength of the Megacorona modulo 10⁹+7.

Constraints:

• 1 < T < 10⁵
• 1 < N < 10⁵

Test Files:

Test File #1 (20 points):

• 1 < N < 10
• Sum of N over all test cases does not exceed 10⁶

Test File #2 (40 points):

• Sum of N over all test cases does not exceed 10⁶

Test File #3 (40 points): original constraints