P4910 Patchouli’s Bracelet.

Patchouli is an old friend of Remilia. She now lives in the large library in the basement of the Scarlet Devil Mansion. She is good at many kinds of magic, and she also creates new magic every day. However, her body is weak. Because of asthma, she may run into trouble when chanting spell cards. The elemental magic she uses has seven attributes: “Wood” for life and awakening, “Fire” for change and activity, “Earth” for foundation and stillness, “Metal” for fruits and harvest, “Water” for silence and purification, “Sun” for mobility and attack, and “Moon” for passiveness and defense. The windowless library may be full of dust, but she believes she belongs by the books, so she cannot leave their side. This has been the case for a hundred years.

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$.

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.

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

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