"Go Beyond, Plus Ultra" - All Might
Midoriya is having a hard time to control his quirk 'One for All'. Recently in his fight with Muscular, A villain he severely damaged his arms. Now Midoriya needs to take precautions otherwise his body can't take the impact anymore and he won't be able to become the greatest hero of all time. Confronted by a villain midoriya needs N shots to defeat the enemy. He has 3 varieties of attacks to deliver in one shot:
A: (Alpha destroyer smasher) A super special move that places enormous pressure on his arms and villain hopes to win are completely turned to zero.
L: (LostWayne Smash) A destructive punch enough to break enemies jaw
P: (Puma Smash) Don't be amazed by its name this move is just a simple kick without any power.
A shot sequence is safe if it doesn't contain more than one Alpha destroyer or more than two continuous Lostwayne Smash.
Can you help midoriya know the number of safe shot sequences he can make?
The answer may be very large, return it after mod 109 + 7.
INPUT FORMAT:
The first line contains 'T' = no. of test cases.
Each testcase contains 1 line -
One Integer N as described in the problem statement.
OUTPUT FORMAT:
For each testcase, print a single integer representing the number of ways Midoriya can shot.
CONTRAINTS:
For 60% Test Cases
1 <= T <= 105
1 <= N <= 105
For 40% Test Cases
1 <= T <= 105
1 <= N <= 109
There are 8 possible shot sequences with length 2 that will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times
