All submissions for this problem are available.
Leonardo has trained a new army to defend the town of Vinci. These soldiers are skilled in the use of swords, spears and bows. It was decided that they will fight the next battle in a 3 * N grid formation.
These soldiers haven't yet been given their weapons for the upcoming battle. Each soldier can be given a sword, spear or a bow. Each soldier has mastered all those weapons. Assume that an infinite supply of each type of weapon is available. In how many ways can the weapons be distributed such that each soldier gets exactly one weapon and there is no redundancy?
There is a redundancy in a distribution if two adjacent soldiers have the same
weapon. Two soldiers are adjacent if they are beside each other or if one is in front of or behind the other in the grid formation.
Two ways of distributing the weapons are considered different if there is atleast one soldier who gets different weapons.
The first line of input contains a single integer T denoting the number of test cases. The descriptions of the test cases follow. The first and the only line of each test case contains a single integer denoting the value of N
For each test case print, on a new line, the answer to the problem modulo 1000000007 (109 + 7)
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 108
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions