Background

Even if you know the method, you must never change the past. You must never turn a possible existence into a fixed reality. No one can predict the future, and it cannot be redone. Precisely because of this, people can accept all kinds of pain, misfortune, and sudden disasters, and keep moving forward.

Problem Description

For some reason, Rintaro owes Mayuri one banana.

To shut Mayuri up, Rintaro makes a deal with Mayuri: as long as Mayuri answers this question correctly, Mayuri can have as many bananas as she wants:

There are $N$ secret passages in the mechanism. The length of the $i$-th secret passage is $i$. The mechanism will randomly choose some secret passages from the $2^n$ possible selection plans with equal probability. If the selected secret passages can form a convex polygon, then the weight of this plan is the number of selected secret passages; otherwise, the weight is $0$.

Now please compute the expected value of the weight of the selected secret passages modulo $10^9+7$. (Two selection plans are different if and only if there exists a secret passage that is selected in one plan but not selected in the other. Note that the empty set is also a plan.)

Kurisu: Then isn’t this just...

Rintaro: Assistant, shut up!

Mayuri drew and drew on the paper, but ended up drawing nothing. So Mayuri can only ask you for help.

Input Format

The input has $T+1$ lines in total.

The first line contains a positive integer $T$, meaning there are $T$ queries.

The next $T$ lines each contain one positive integer, representing $N$ for this query.

Output Format

Your output should contain exactly $T$ lines. The $i$-th line contains a non-negative integer representing the expected value for the query modulo $10^9+7$.

5
1
2
3
4
5

0
0
0
937500007
562500005

Hint

Sample Explanation 1

It is easy to see that when $n$ is less than or equal to $3$, it is impossible to form a valid polygon.

When $n=4$, the following sets of chosen side lengths have non-zero weight:

$\{1,2,3,4\}$, $\{2,3,4\}$.

The answer is $\frac{7}{16} \equiv 937500007\ (\bmod 1000000007)$.

When $n=5$, the following sets of chosen side lengths have non-zero weight:

$\{1,2,3,4\}$, $\{2,3,4\}$, $\{1,2,3,5\}$, $\{2,3,4,5\}$

$\{1,3,4,5\}$, $\{1,2,4,5\}$, $\{2,4,5\}$, $\{3,4,5\}$, $\{1,2,3,4,5\}$.

The answer is $\frac{34}{32} \equiv 562500005\ (\bmod 1000000007)$.

Subtasks

This problem uses bundled testdata.

For $100\%$ of the data, $1\leq n\leq 5000$, $1\leq T \leq 5000$.

There are $5$ subtasks in total. The score and limits of each subtask are as follows:

Subtask $1$ ($20$ points): $1 \leq n \leq 10$.

Subtask $2$ ($30$ points): $1 \leq n \leq 20$.

Subtask $3$ ($15$ points): $1 \leq n \leq 50$.

Subtask $4$ ($15$ points): $1 \leq n \leq 300$.

Subtask $5$ ($20$ points): no special restrictions.

Source

MtOI2019 Extra Round T3

Problem setter: CYJian

Checker: suwAKow

Translated by ChatGPT 5