Chef is interested to solve series problems. Chef wants to solve a series problem but he can't 
solve it till now.Can you help Chef to solve the series problem?
- In series problem, the series goes as follows 1,9,31,73,141 . . . . . . . . 
Your task is to find the Nth term of series. For larger value of $N$ answer becomes very large, So your output should be performed $N$th term modulo 1000000007 ($10^9+7$ ).

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single integer $N$. 

-----Output:-----
For each testcase,  output in a single line answer i.e. The $N$th term of series modulo 1000000007.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^9$

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

8

10

-----Sample Output:-----
561

1081

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
try:
	for t in range(int(input())):
		n = int(input())
		ans = n * n * n + (n - 1) ** 2
		if ans <= 10 ** 9 + 7:
			print(ans)
		else:
			print(ans) % (10 ** 9 + 7)
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	s = n ** 3 + (n - 1) ** 2
	print(s % 1000000007)


series = []
series.append(0)
i = 1
j = 2
for i in range(1, 10000007):
	series.append(i * i + j * j * j)
	i = i + 1
	j = j + 1
t = int(input())
while t > 0:
	n = int(input())
	print(series[n - 1] % 1000000007)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(n)
	elif n < 0:
		print(0)
	else:
		print(((n - 1) * (n - 1) + n * n * n) % 1000000007)


for _ in range(int(input())):
	n = int(input())
	arr = [1, 9, 31]
	diff = [8, 22]
	if n == 1:
		print(arr[0])
	elif n == 2:
		print(arr[1])
	elif n == 3:
		print(arr[-1])
	else:
		has = 0
		for i in range(2, n - 1):
			value = diff[i - 1] - diff[i - 2]
			value = value + 6
			value = value + diff[-1]
			diff.append(value)
			value = value + arr[-1]
			arr.append(value)
		print(arr[-1] % (10 ** 9 + 7))


for tc in range(int(input())):
	n = int(input())
	t = n ** 3 + (n - 1) ** 2
	print(t % 1000000007)


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
mod = 1000000007
for _ in range(t):
	n = int(input())
	ans = power(n - 1, 2, mod) + power(n, 3, mod)
	print(ans % mod)


for _ in range(int(input())):
	n = int(input())
	result = n ** 3 + (n - 1) ** 2
	result = result % 1000000007
	print(result)


t = int(input())
while t > 0:
	n = int(input())
	ans = (n - 1) * (n - 1) + n * n * n
	print(ans % 1000000007)
	t = t - 1


try:
	for _ in range(int(input())):
		n = int(input())
		r = n ** 3 + (n - 1) ** 2
		print(r % 1000000007)
except:
	pass


import math
for _ in range(int(input())):
	n = int(input()) - 1
	nth = math.pow(n, 2) + math.pow(n + 1, 3)
	print(int(nth % 1000000007))


for u in range(int(input())):
	n = int(input())
	s = (n - 1) ** 2 + n ** 3
	print(s % (10 ** 9 + 7))


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		M = 1000000007
		d = n ** 3
		f = (n - 1) ** 2
		g = (d + f) % M
		print(g)
except:
	pass


for i in range(int(input())):
	x = int(input())
	a = x * x * x + (x - 1) * (x - 1)
	print(a % 1000000007)


for i in range(int(input())):
	n = int(input())
	res = pow(n - 1, 2) + pow(n, 3)
	print(res % 1000000007)


t = int(input())
for i in range(t):
	n = int(input())
	x = [1]
	for i in range(1, n):
		p = (i ** 2 + (i + 1) ** 3) % 1000000007
		x.append(p)
	print(x[n - 1])


T = int(input())
while T > 0:
	N = int(input())
	T = T - 1
	A = (N - 1) ** 2 + N ** 3
	print(A % 1000000007)


for i in range(int(input())):
	n = int(input())
	x = (n - 1) ** 2 + n ** 3
	if x > 1000000000:
		x = x % 1000000007
	print(x)


from math import sqrt
for _ in range(int(input())):
	(N, MOD) = (int(input()), 1000000007)
	print((N - 1) ** 2 + N ** 3 % MOD)


x = pow(10, 9) + 7
for i in range(int(input())):
	n = int(input())
	ans = pow(n, 3) + pow(n - 1, 2)
	print(ans % x)