Milly with strings
Problem
Milly is playing with some random strings. She is trying to build some strings of length N using characters from set { P, L, M }. There is an infinite supply of these characters. She hates those strings which do not contain "PLM" as its substring so she wants to know the total count of the strings of length N that does not have "PLM" as its substring. Since this count may be quite large, output the answer modulo 109 + 7.
Input
First line of the input will contains T ( number of test cases). Each of next T lines contains an integer N.Output
For each test case, output the number of asked strings of length N.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 105
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
In the 2nd test case, total 27 strings of length 3 are possible and only string “PLM” will not be counted . Hence the answer is 26.
