Problem Background

Patchouli is an old friend of Remilia and currently resides in the large library beneath the Scarlet Devil Mansion. She is adept in many magics and develops new spells daily. However, her health is frail, and she struggles with asthma when reciting her spell cards.

Her elemental magic primarily consists of "Wood" for life and awakening, "Fire" for change and activity, "Earth" for foundation and stability, "Metal" for fruitfulness and harvest, "Water" for silence and purification, "Sun" for mobility and offense, and "Moon" for passivity and defense.

The windowless library might be filled with dust, but she believes she belongs by the books, and thus cannot leave their side. This has been the case for a century.

Problem Description

After years of magical accumulation, Patchouli has condensed a portion of her vast magic into special beads.

Due to her love for peace, she only included the wood and metal elemental magics in these beads.

She felt that these beads alone were not useful, so she decided to string them into a magical bracelet, which would be much more aesthetically pleasing. Therefore, she brought out the thread for stringing these beads - Misty Rain Path.

After stringing the beads together, she discovered a property: the color of a segment of Misty Rain Path is determined by the attributes of the beads on either side. If either of the two beads connected by a segment is metal, then the color of that segment is gold.

Patchouli wants a bracelet entirely of gold color and would like to know how many possible arrangements there are. Since she is busy researching new magic, she has entrusted this task to you. Given her vast magic, she has an infinite number of beads.

She does not want to deal with numbers with dozens of digits, so you need to take the modulo of $1000000007$.

Input and Output Formats

Input Format

The input contains multiple sets of data.

The first line contains a positive integer $T$, representing the number of data sets.

Each subsequent line contains an integer $n$, representing the total number of wood and metal beads.

Output Format

For each set of data, output the number of possible arrangements modulo $1000000007$.

Sample Input and Output

Sample Input #1

2
5
20

Sample Output #1

11
15127

Sample Input #2

3
9
99
999

Sample Output #2

76
281781445
445494875

Sample Input #3

5  
123
1234
12345
123456
1234567

Sample Output #3

528790589
200102666
537707871
262341000
534036342

Notes

Here is an explanation for the sample when $n = 5$:

Using $1, 2, 3, 4, 5$ to represent each bead, the feasible arrangements are:

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

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

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

For $20\%$ of the data, $1 \le n \le 10$;

For $40\%$ of the data, $1 \le n \le 10^2$;

For $60\%$ of the data, $1 \le n \le 10^6$;

For $90\%$ of the data, $1 \le n \le 10^9$;

For all data, $1 \le T \le 10, 1 \le n \le 10^{18}$.

见题面 Input 部分

见题面 Output 部分