Ben is obsessed with names. He only likes names that:

• Are of length N 
• Do not contain palindromic substrings of even lengths. The name can only consist of lowercase alphabets.

Help Ben determine the number of interesting names. Since this number can be very large compute it modulo $(10^9 +7)$.

Notes

• A palindrome is a sequence of characters that reads the same backward and forward. For example, madam or civic.
• If N = 4, "abab" is an interesting name, while "abba" is not an interesting name as it contains "bb" and "abba" as substrings that are palindromes of even length.

Input format

• Each test contains multiple test cases. The first line contains the number of test cases T.
• The first and only line of each test case contains a single integer N representing the length of the name that Ben likes.

Output format

For each test case, print a single line containing one integer number of interesting names modulo $(10^9 +7)$.

Constraints

$1 ≤T ≤ 10^4 \\ 1 ≤ N ≤ 10^5\\ \text{It is guaranteed that the sum of N across all test cases does not exceed }2\cdot 10^5$