Read problems statements in Mandarin Chinese  and Russian. 

As we all know, Binomial Coefficient C(n, r) is defined by the
following formula. 

Also define S(n) as follows. 

Note that n will be provided to you as an input parameter.

Since S(n) can be very large, please print it modulo (10^{9} + 7).

------ Input ------ 

The first line contains a single integer T representing the number of test cases.
Each of the next T lines contains an integer n.

------ Output ------ 

For each test case, output a single line containing the value of S(n) modulo (10^{9} + 7). 

------ Constraints ------ 

10 points:
1 ≤ T ≤ 300
1 ≤ n ≤ 300

30 points:
1 ≤ T ≤ 10^{5}
1 ≤ n ≤ 5000

60 points:
1 ≤ T ≤ 10^{5}
1 ≤ n ≤ 10^{18}

------ Example ------ 

Input:
5
1
2
3
4
5

Output:
2
4
2
4
8

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
for t in range(int(input())):
	n = int(input())
	c = [0] * 3
	while n != 0:
		c[n % 3] += 1
		n //= 3
	print(int(2 ** (c[1] - 1) * (3 ** (c[2] + 1) - 1)) % (10 ** 9 + 7))


for _ in range(int(input())):
	n = int(input())
	cnt = [0 for i in range(3)]
	while n != 0:
		res = n % 3
		n //= 3
		cnt[res] += 1
	print(int(2 ** (cnt[1] - 1) * (3 ** (cnt[2] + 1) - 1)) % (10 ** 9 + 7))


def baseN(num, b, numerals='0123456789abcdefghijklmnopqrstuvwxyz'):
	return num == 0 and numerals[0] or baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b]
MOD = 10 ** 9 + 7

def solve(n):
	(x, r, s) = (baseN(n, 3), 0, 0)
	for i in range(len(x)):
		if x[i] == '1':
			r += 1
		if x[i] == '2':
			s += 1
	if r >= 1:
		v1 = pow(2, r - 1, MOD)
	else:
		v1 = pow(2, r - 1)
	print(int((v1 * (pow(3, s + 1, MOD) - 1) + MOD) % MOD))
for i in range(int(input())):
	solve(int(input()))


cnt = [0 for i in range(0, 3)]

def convert(n):
	while n:
		cnt[n % 3] = cnt[n % 3] + 1
		n = n // 3
t = int(input())
for i in range(0, t):
	n = int(input())
	cnt[0] = 0
	cnt[1] = 0
	cnt[2] = 0
	convert(n)
	print(int(2 ** (cnt[1] - 1) * (3 ** (cnt[2] + 1) - 1)) % (10 ** 9 + 7))