Description

After years of magical practice, Patchouli has condensed part of her vast magic into some special beads.

Because Patchouli loves peace, she only put Wood-attribute magic (which stands for life and awakening) and Metal-attribute magic (which stands for fruits and harvest) into the beads.

She thinks that having only these beads is not very useful, so she wants to string them into a magic bracelet, which looks much better. So she took out the thread used to string these beads, called Kirisame Spirit Path (Wuyu Lingjing).

After stringing the beads together, she found a property: as long as at least one of two adjacent beads is Metal-attribute, then the Kirisame Spirit Path between them will be colored gold.

Patchouli wants a bracelet whose thread segments are all gold, and she also wants to know how many different ways there are. Since she still needs to research new magic, she leaves this task to you. Because her magic is vast, she has infinitely many beads.

She does not want to look at a number with dozens of digits, so you need to take the result modulo $1000000007$.

Input Format

The input contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

Then for each test case, a single integer $n$ is given, representing the total number of Wood-attribute beads and Metal-attribute beads.

Output Format

For each test case, output the number of valid ways modulo $1000000007$.

2
5
20

11
15127

3
9
99
999

76
281781445
445494875

5  
123
1234
12345
123456
1234567

528790589
200102666
537707871
262341000
534036342

Hint

Here is the explanation of the sample when $n = 5$:

Use $1, 2, 3, 4, 5$ to represent the beads.

Valid ways are (the numbers denote the indices of beads dyed as the Metal element):

$\{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 testdata, $1 \le n \le 10$.

For $40\%$ of the testdata, $1 \le n \le 10^2$.

For $60\%$ of the testdata, $1 \le n \le 10^6$.

For $90\%$ of the testdata, $1 \le n \le 10^9$.

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

Translated by ChatGPT 5