IIIT-Delhi has been invaded by aliens. An alien race from a galaxy far away is shooting a beam on the Academic Block of IIIT-Delhi. Everyone is frightened by this attack. On each day a beam is shot on roof of Academic Block and there is great shaking in the block. IIIT-Delhi AlienAttack team has decided to make a layer to be put up on roof of the Academic block which can absorb this beam and thus protect the block from the beam. The AlienAttack team knows how to make this layer but for this they need to know the strength of beam falling on this layer. Babulal, guard of IIIT-Delhi has analysed the strength of beam and has found that the strength of beam on any day is the strength of beam on the previous day plus the twice the strength of beam on the day before previous day. Babulal then shared this analysis with the team. Now considering Babulal’s analysis AlienAttack team has to find the strength of the beam on Day N. So, consider yourself a part of the team and give the minimum strength that the layer should have to protect the block against the beam.
Given the strength of beam on day one is 2 megapower and on day two is 7 megapower, you have to find the strength on day N. As the value of strength on Day N can be very large print the result modulo 10^9 + 7.
Note :
1. Megapower is the unit of strength.
2. Building hasn't fallen down after the attack on first two days and after that you have to save the building.
3. Minimum strength of layer required on day N is equal to the strength of beam on day N.
4. Babulal’s analysis is correct, smart guard.


Input :
First line of input will contain a single integer T representing number of test cases. Each of next T lines will contain a single integer N representing the day number of which you have to calculate the minimum strength of layer required.

Output :
Output will contain T lines each having a single integer representing the strength of beam on day N modulo 10^9 +7.

Constraints:
1<=T<=100
1<=N<=10^8