Medium
Divide and Conquer > Dynamic Programming

**Amedeus Cho** helped **Bruce Banner** survive a radiation explosion and in the process he was exposed to the gamma radiation, becoming the “Totally Awesome Hulk”. Amedeus , with the help of his genious sister Madame Cho, roams in New York and fights crime with a chilled mood, turning into a jolly yet gruesome Hulk. Amedues is ranked as the 8th smartest person in the Marvel Universe, behind Hank Pym, Moon Girl, Bruce Banner, Tony Stark, Hank McCoy, Dr.Doom, T’Chala. But Madame Cho thinks her brother is naive and not smarter than her. To test Amedeus’s intelligence, she thought of a mathematical question.
And here she is, Madame Cho, asking him the question,
“ Let us call a **n-digit** number (n is an integer , **1<=n<=100000**) a Meme-number if it consists of digits from **0,1,2,3,4** and the difference between any two consecutive digit in the number is exactly two. How many n-digit numbers are there who are Meme-numbers?”
Input:
------
Input will consist of N+1 lines in separate line ( **1<=N <=100000**)
First line will contain N, the number of values of **n**.
Next N line will contain one integer each denoting the value of n.
Output:
-------
For each n, print the number of n-digit numbers which are Meme-numbers. You should print the answer modulo **10^9+7**.
Sample Input
------------
2
1
2
Sample Output
-------------
5
6
Explanation:
There are 2 inputs: n=1,2
For n=1, possible Meme-numbers are { 0, 1, 2, 3, 4}=>5
For n=2, possible Meme-numbers are {20, 31, 02, 42,13, 24}=>6

#### Please login to submit solution to this problem.