Our chef has been assigned a task to make a necklace of length N, from gold, diamond and platinum.There is single kind of gold, two types of diamond and three types of platinum available.
A necklace can be represented as strings of the form (G)∗(D1|D2)∗(P1|P2|P3)∗$ (G)*(D1|D2)*(P1|P2|P3)* $ where (x|y) means we can use x or y and ∗$ * $ means we can repeat the previous parenthesized expression 0 or more times.
Instead of making necklace he choose to count all such distinct necklaces possible for a given length N.

-----Input:-----
-The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
-Only line of every test case contains an integer N$N$ denoting the length of the necklace required.

-----Output:-----
For each test case, print the number of all such distinct necklaces, with given length. As the number can be really large, print it modulo  109+7$10^{9}+7$.

-----Constraints-----
- 1≤T≤10000$1 \leq T \leq 10000$
- 2≤N≤1000000000$2 \leq N \leq 1000000000$
- String S$S$ consists of only upper case english alphabets.

-----Subtasks-----
- 20 points : 1≤N≤5$1 \leq N \leq 5$
- 70 points : Original$Original$ Constraints$Constraints$

-----Sample Input:-----
2
1
2

-----Sample Output:-----
6
25

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	p = 10 ** 9 + 7
	a = pow(3, n + 1, p) - 1
	b = pow(2, n + 1, p) - 1
	print((3 * a // 2 % p - 2 * b % p + p) % p)


tc = int(input())
while tc > 0:
	tc -= 1
	mod_inv = 500000004
	mod = 1000000007
	n = int(input())
	res = 4500000036 * (pow(3, n, mod) - 1) % mod - 4 * (pow(2, n, mod) - 1)
	print((res + 1) % mod)


import math
import bisect
import itertools
import sys
mod = 10 ** 9 + 7
a1 = [2, 6]
a2 = [3, 18]
a = []
for i in range(100000):
	a2.append((a2[-1] + a1[-1] + 1) * 3 % mod)
	a1.append((a1[-1] + 1) * 2 % mod)
for i in range(100000):
	a.append((a1[i] + a2[i] + 1) % mod)
t = int(input())
for i in range(t):
	n = int(input())
	print(a[n - 1])


T = int(input())
while T > 0:
	T -= 1
	mod_inv = 500000004
	mod = 1000000007
	n = int(input())
	ans = 4500000036 * (pow(3, n, mod) - 1) % mod - 4 * (pow(2, n, mod) - 1)
	print((ans + 1) % mod)


t = int(input())
mod = 10 ** 9 + 7
inverse = 5 * 10 ** 8 + 4
for i in range(t):
	n = int(input())
	temp1 = pow(3, n + 2, mod)
	temp2 = pow(2, n + 3, mod)
	a = (temp1 - temp2 + 1) % mod
	a = a * inverse % mod
	print(a)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	c = 0
	for j in range(n + 1):
		for k in range(0, n - j + 1):
			c += 2 ** k * 3 ** j
	ans.append(c)
for i in ans:
	print(i)


t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	n = int(input())
	ans = 0
	for j in range(n + 1):
		temp1 = pow(3, j, mod)
		temp2 = (pow(2, n + 1 - j, mod) + (mod - 1)) % mod
		temp3 = temp1 * temp2 % mod
		ans = (ans + temp3) % mod
	print(ans)


t = int(input())
mod = 1000000007
while t:
	t -= 1
	n = int(input())
	ans = 2 * pow(3, n + 1, mod) % mod - pow(2, n + 2, mod) - (pow(3, n + 1, mod) - 1) * 500000004 % mod
	ans %= mod
	print(ans)


MOD = int(1000000000.0 + 7)
for _ in range(int(input())):
	n = int(input()) + 1
	res = (3 * pow(3, n, MOD) - 3) % MOD * 500000004 % MOD
	res = (res - 2 * (pow(2, n, MOD) - 1) % MOD) % MOD
	print(res)


T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	ans = 0
	for i in range(n + 1):
		for j in range(n - i + 1):
			k = n - i - j
			ans += pow(2, j, 1000000007) * pow(3, k, 1000000007) % 1000000007
	print(ans)