Kulyash has given you a bag with (N + M) balls having distinct colours. Among these, N balls have the number 2 printed on them and M balls have the number 0 printed on them.

He defines the *score* of a non-empty subset S of these (N + M) balls as:  
(sum of the balls in S)  - (size of S).

Find the count of non-empty subsets of these (N + M) balls having their *scores* divisible by 3. Since the answer can be huge, output it modulo 10^{9} + 7.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two space-separated integers N and M — the number balls having 2 and the number of balls having 0 respectively.

------ Output Format ------ 

For each test case, output on a new line, the number of non-empty subsets having scores divisible by 3, modulo 10^{9} + 7.

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

$1 ≤ T ≤ 10^{3}$
$0 ≤ N, M ≤ 10^{9}$

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

----- Sample Output 1 ------ 
1
5

----- explanation 1 ------ 
Test case $1$: The only non-empty subset having score divisible by $3$ is $[2, 0]$. The score of this subset is $(2 + 0) - (2) = 0$, which is divisible by $3$. So, the answer is $1$.

Test case $2$: There are $2$ types of subsets having scores divisible by $3$: $[2,0]$ and $[2,2,0,0]$. The first type of subset can for formed in $4$ ways (there are two $2$s and two $0$s) and the second type can be formed in only $1$ way. So, the answer is $5$.

Difficulty: HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
from math import comb
mod = int(1000000000.0 + 7)

def powe(base, exp):
	ans = 1
	while exp:
		if exp & 1:
			ans = ans * base % mod
		base = base * base % mod
		exp //= 2
	return ans

def inverse(base):
	return powe(base, mod - 2)

def handle0(n):
	inte = n % 6
	if n % 6 == 0:
		return 2
	elif inte == 1:
		return 1
	elif inte == 2:
		return -1
	elif inte == 3:
		return -2
	elif inte == 4:
		return -1
	else:
		return 1

def handle1(n):
	inte = n % 6
	if n % 6 == 0:
		return -1
	elif inte == 1:
		return 1
	elif inte == 2:
		return 2
	elif inte == 3:
		return 1
	elif inte == 4:
		return -1
	else:
		return -2

def handle2(n):
	inte = n % 6
	if n % 6 == 0:
		return -1
	elif inte == 1:
		return -2
	elif inte == 2:
		return -1
	elif inte == 3:
		return 1
	elif inte == 4:
		return 2
	else:
		return 1

def solver(a, b):
	a0 = (handle0(a) + powe(2, a)) * inverse(3) % mod
	a1 = (handle1(a) + powe(2, a)) * inverse(3) % mod
	a2 = (handle2(a) + powe(2, a)) * inverse(3) % mod
	b0 = (handle0(b) + powe(2, b)) * inverse(3) % mod
	b1 = (handle1(b) + powe(2, b)) * inverse(3) % mod
	b2 = (handle2(b) + powe(2, b)) * inverse(3) % mod
	print(((a0 * b0 + a1 * b1 + a2 * b2) % mod + mod - 1) % mod)

def main():
	t = int(input())
	while t:
		k = input()
		k = k.split()
		solver(int(k[0]), int(k[1]))
		t -= 1
main()


def power(b, n):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % MOD
		b = b * b % MOD
		n //= 2
	return s

def Inv(x):
	return power(x, MOD - 2)
MOD = 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [0, 0, 0]
	b = [0, 0, 0]
	a[0] = ([2, 1, -1, -2, -1, 1][n % 6] + power(2, n)) * Inv(3) % MOD
	a[1] = ([-1, 1, 2, 1, -1, -2][n % 6] + power(2, n)) * Inv(3) % MOD
	a[2] = ([-1, -2, -1, 1, 2, 1][n % 6] + power(2, n)) * Inv(3) % MOD
	b[0] = ([2, 1, -1, -2, -1, 1][m % 6] + power(2, m)) * Inv(3) % MOD
	b[1] = ([-1, 1, 2, 1, -1, -2][m % 6] + power(2, m)) * Inv(3) % MOD
	b[2] = ([-1, -2, -1, 1, 2, 1][m % 6] + power(2, m)) * Inv(3) % MOD
	print(((a[0] * b[0] + a[1] * b[1] + a[2] * b[2]) % MOD + MOD - 1) % MOD)


mod = 1000000007
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	x = [2, 1, -1, -2, -1, 1]
	y = [-1, 1, 2, 1, -1, -2]
	a0 = (pow(2, n, mod) + x[n % 6]) * pow(3, mod - 2, mod) % mod
	a1 = (pow(2, n, mod) + y[n % 6]) * pow(3, mod - 2, mod) % mod
	a2 = (pow(2, n, mod) - a0 - a1) % mod
	b0 = (pow(2, m, mod) + x[m % 6]) * pow(3, mod - 2, mod) % mod
	b1 = (pow(2, m, mod) + y[m % 6]) * pow(3, mod - 2, mod) % mod
	b2 = (pow(2, m, mod) - b0 - b1) % mod
	ans = (a0 * b0 + a1 * b1 + a2 * b2 - 1) % mod
	print(ans)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	(a, b) = [[[2, 1, -1, -2, -1, 1][n % 6] + pow(2, n, 1000000007), [-1, 1, 2, 1, -1, -2][n % 6] + pow(2, n, 1000000007), [-1, -2, -1, 1, 2, 1][n % 6] + pow(2, n, 1000000007)], [[2, 1, -1, -2, -1, 1][m % 6] + pow(2, m, 1000000007), [-1, 1, 2, 1, -1, -2][m % 6] + pow(2, m, 1000000007), [-1, -2, -1, 1, 2, 1][m % 6] + pow(2, m, 1000000007)]]
	print(((a[0] * b[0] + a[1] * b[1] + a[2] * b[2]) * 111111112 + 1000000006) % 1000000007)


os = [[1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [0, 0, 1], [1, 0, 1]]
p = 10 ** 9 + 7

def razn(x, y):
	return (x - y) % p

def slog(x, y):
	return (x + y) % p

def mult(x, y):
	return x * y % p

def pow(x, y):
	s = x
	res = 1
	while y > 0:
		a = y % 2
		if a:
			res = mult(res, s)
		s = mult(s, s)
		y = y // 2
	return res

def delen(x, y):
	return mult(x, pow(y, p - 2))

def rasp(n):
	if n % 2:
		e = 2
	else:
		e = 1
	w = delen(razn(pow(2, n), e), 3)
	res = [w, w, w]
	q = os[n % 6]
	for i in range(3):
		res[i] += q[i]
	return res
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = rasp(n)
	b = rasp(m)
	otv = 0
	for x in range(3):
		otv = slog(otv, mult(a[x], b[x]))
	otv = razn(otv, 1)
	print(otv)


MOD = 10 ** 9 + 7

def calPower(i, j):
	sums = 1
	while j:
		if j % 2 == 1:
			sums = sums * i % MOD
		i = i * i % MOD
		j //= 2
	return sums

def inverse(n):
	return calPower(n, MOD - 2)
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	arrA = [0 for _ in range(3)]
	arrB = [0 for _ in range(3)]
	arrA[0] = ([2, 1, -1, -2, -1, 1][N % 6] + calPower(2, N)) * inverse(3) % MOD
	arrA[1] = ([-1, 1, 2, 1, -1, -2][N % 6] + calPower(2, N)) * inverse(3) % MOD
	arrA[2] = ([-1, -2, -1, 1, 2, 1][N % 6] + calPower(2, N)) * inverse(3) % MOD
	arrB[0] = ([2, 1, -1, -2, -1, 1][M % 6] + calPower(2, M)) * inverse(3) % MOD
	arrB[1] = ([-1, 1, 2, 1, -1, -2][M % 6] + calPower(2, M)) * inverse(3) % MOD
	arrB[2] = ([-1, -2, -1, 1, 2, 1][M % 6] + calPower(2, M)) * inverse(3) % MOD
	print(((arrA[0] * arrB[0] + arrA[1] * arrB[1] + arrA[2] * arrB[2]) % MOD + MOD - 1) % MOD)


import math
MOD = 1000000007

def power(b, n):
	r = 1
	while n:
		if n % 2 == 1:
			r = r * b % MOD
		b = b * b % MOD
		n = n // 2
	return r

def Inv(x):
	return power(x, MOD - 2)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	r = 0
	a = [0 for _ in range(3)]
	b = [0 for _ in range(3)]
	a0 = [2, 1, -1, -2, -1, 1]
	a1 = [-1, 1, 2, 1, -1, -2]
	a2 = [-1, -2, -1, 1, 2, 1]
	b0 = [2, 1, -1, -2, -1, 1]
	b1 = [-1, 1, 2, 1, -1, -2]
	b2 = [-1, -2, -1, 1, 2, 1]
	a[0] = (a0[n % 6] + power(2, n)) * Inv(3) % MOD
	a[1] = (a1[n % 6] + power(2, n)) * Inv(3) % MOD
	a[2] = (a2[n % 6] + power(2, n)) * Inv(3) % MOD
	b[0] = (b0[m % 6] + power(2, m)) * Inv(3) % MOD
	b[1] = (b1[m % 6] + power(2, m)) * Inv(3) % MOD
	b[2] = (b2[m % 6] + power(2, m)) * Inv(3) % MOD
	print(((a[0] * b[0] + a[1] * b[1] + a[2] * b[2]) % MOD + MOD - 1) % MOD)


for _ in range(int(input())):
	(N, M) = map(int, input().split(' '))
	modulo = 10 ** 9 + 7
	my_sum = pow(2, N + M, modulo)
	special = 1 if (M - N) % 3 == 0 else 0
	if (N + M) % 2 == 0:
		result = (my_sum - 1) * pow(3, -1, modulo) + special - 1
	else:
		result = (my_sum + 1) * pow(3, -1, modulo) - special - 1
	print(result % modulo)


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	mod = 1000000007
	x = 111111112
	y = 1000000006
	(p, q) = [[[2, 1, -1, -2, -1, 1][N % 6] + pow(2, N, mod), [-1, 1, 2, 1, -1, -2][N % 6] + pow(2, N, mod), [-1, -2, -1, 1, 2, 1][N % 6] + pow(2, N, mod)], [[2, 1, -1, -2, -1, 1][M % 6] + pow(2, M, mod), [-1, 1, 2, 1, -1, -2][M % 6] + pow(2, M, mod), [-1, -2, -1, 1, 2, 1][M % 6] + pow(2, M, mod)]]
	print(((p[0] * q[0] + p[1] * q[1] + p[2] * q[2]) * x + y) % mod)


def po(b, k):
	s = 1
	while k:
		if k % 2 == 1:
			s = s * b % 1000000007
		b = b * b % 1000000007
		k = k // 2
	return s

def iv(x):
	return po(x, 1000000007 - 2)

def kar():
	(n, m) = map(int, input().split())
	(a, b) = ([], [])
	a.append(([2, 1, -1, -2, -1, 1][n % 6] + po(2, n)) * iv(3) % 1000000007)
	a.append(([-1, 1, 2, 1, -1, -2][n % 6] + po(2, n)) * iv(3) % 1000000007)
	a.append(([-1, -2, -1, 1, 2, 1][n % 6] + po(2, n)) * iv(3) % 1000000007)
	b.append(([2, 1, -1, -2, -1, 1][m % 6] + po(2, m)) * iv(3) % 1000000007)
	b.append(([-1, 1, 2, 1, -1, -2][m % 6] + po(2, m)) * iv(3) % 1000000007)
	b.append(([-1, -2, -1, 1, 2, 1][m % 6] + po(2, m)) * iv(3) % 1000000007)
	print(((a[0] * b[0] + a[1] * b[1] + a[2] * b[2]) % 1000000007 + 1000000007 - 1) % 1000000007)
t = int(input())
for h in range(t):
	kar()


MOD = 10 ** 9 + 7
thrinv = pow(3, -1, MOD)

def carve(n, i):
	sculp = pow(2, n, MOD) - n % 2 - 1
	if (n + ((i << 2) + 1)) % 6 < 3:
		sculp += 3
	return sculp * thrinv % MOD

def main(N, M):
	subsets = -1
	for i in range(3):
		ns = carve(N, i)
		ms = carve(M, i)
		subsets += ns * ms % MOD
	return subsets % MOD
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	print(main(N, M))


MOD = 1000000007

def o(a1, a2):
	t = 1
	while a2:
		if a2 % 2 == 1:
			t = t * a1 % MOD
		a1 = a1 * a1 % MOD
		a2 //= 2
	return t

def i(x):
	return o(x, MOD - 2)
l1 = [0] * 3
l2 = [0] * 3
for t in range(int(input())):
	(n, m) = map(int, input().split())
	l1[0] = ([2, 1, -1, -2, -1, 1][n % 6] + o(2, n)) * i(3) % MOD
	l1[1] = ([-1, 1, 2, 1, -1, -2][n % 6] + o(2, n)) * i(3) % MOD
	l1[2] = ([-1, -2, -1, 1, 2, 1][n % 6] + o(2, n)) * i(3) % MOD
	l2[0] = ([2, 1, -1, -2, -1, 1][m % 6] + o(2, m)) * i(3) % MOD
	l2[1] = ([-1, 1, 2, 1, -1, -2][m % 6] + o(2, m)) * i(3) % MOD
	l2[2] = ([-1, -2, -1, 1, 2, 1][m % 6] + o(2, m)) * i(3) % MOD
	print(((l1[0] * l2[0] + l1[1] * l2[1] + l1[2] * l2[2]) % MOD + MOD - 1) % MOD)


def raised(b, max_power):
	s = 1
	while max_power != 0:
		if max_power % 2 == 1:
			s = s * b % mod
		b = b ** 2 % mod
		max_power = int(max_power / 2)
	return s

def multi(m_arg):
	return raised(m_arg, mod - 2)
for test_loop in range(int(input())):
	mod = 1000000007
	(max_power, max_range) = list(map(int, input().split()))
	arr1 = [0] * 3
	arr2 = [0] * 3
	np_value = raised(2, max_power)
	mp_value = raised(2, max_range)
	multiplier = multi(3)
	zeroth = [2, 1, -1, -2, -1, 1]
	first = [-1, 1, 2, 1, -1, -2]
	second = [-1, -2, -1, 1, 2, 1]
	akey = max_power % 6
	bkey = max_range % 6
	a0 = zeroth[akey] + np_value
	a1 = first[akey] + np_value
	a2 = second[akey] + np_value
	b0 = zeroth[bkey] + mp_value
	b1 = first[bkey] + mp_value
	b2 = second[bkey] + mp_value
	arr1[0] = a0 * multiplier % mod
	arr1[1] = a1 * multiplier % mod
	arr1[2] = a2 * multiplier % mod
	arr2[0] = b0 * multiplier % mod
	arr2[1] = b1 * multiplier % mod
	arr2[2] = b2 * multiplier % mod
	final_cal = arr1[0] * arr2[0] + arr1[1] * arr2[1] + arr1[2] * arr2[2]
	t = (final_cal % mod + mod - 1) % mod
	print(t)


TENP7 = 1000000007
THREE_MODINV_SQ = 111111112

def rotate(l, n):
	return l[n:] + l[:n]
coeff = [-1, -2, -1, 1, 2, 1]
coeff = [coeff, [-x for x in rotate(coeff, 1)], rotate(coeff, 2)]

def pow(base, exp):
	base %= TENP7
	res = 1
	while exp > 0:
		if exp & 1:
			res *= base % TENP7
		base *= base % TENP7
		exp >>= 1
	return res

def solve():
	(n, m) = map(int, input().split(' '))
	ss_count_n = pow(2, n)
	ss_count_m = pow(2, m)
	n %= 6
	m %= 6
	res = 0
	for i in range(3):
		res += (coeff[i][n] + ss_count_n) * (coeff[i][m] + ss_count_m) * THREE_MODINV_SQ % TENP7
	print(res % TENP7 - 1)
tt = int(input())
while tt:
	tt -= 1
	solve()


MOD = 1000000007

def pow(arg1, arg2):
	temp = 1
	while arg2:
		if arg2 % 2 == 1:
			temp = temp * arg1 % MOD
		arg1 = arg1 * arg1 % MOD
		arg2 //= 2
	return temp

def invt(x):
	return pow(x, MOD - 2)
lst1 = [0] * 3
lst2 = [0] * 3
for trie in range(int(input())):
	(n, m) = map(int, input().split())
	lst1[0] = ([2, 1, -1, -2, -1, 1][n % 6] + pow(2, n)) * invt(3) % MOD
	lst1[1] = ([-1, 1, 2, 1, -1, -2][n % 6] + pow(2, n)) * invt(3) % MOD
	lst1[2] = ([-1, -2, -1, 1, 2, 1][n % 6] + pow(2, n)) * invt(3) % MOD
	lst2[0] = ([2, 1, -1, -2, -1, 1][m % 6] + pow(2, m)) * invt(3) % MOD
	lst2[1] = ([-1, 1, 2, 1, -1, -2][m % 6] + pow(2, m)) * invt(3) % MOD
	lst2[2] = ([-1, -2, -1, 1, 2, 1][m % 6] + pow(2, m)) * invt(3) % MOD
	print(((lst1[0] * lst2[0] + lst1[1] * lst2[1] + lst1[2] * lst2[2]) % MOD + MOD - 1) % MOD)


import math
beeg = 1000000007
for tea in range(int(input())):
	(n, m) = [int(aaa) for aaa in input().split()]
	pown = pow(2, n, beeg * 3)
	ns = [math.floor((pown + 1) // 3), math.floor((pown + 1) // 3), math.floor((pown + 1) // 3)]
	ns[-n % 3] += (-1) ** n
	powm = pow(2, m, beeg * 3)
	ms = [math.floor((powm + 1) // 3), math.floor((powm + 1) // 3), math.floor((powm + 1) // 3)]
	ms[-m % 3] += (-1) ** m
	print(math.floor(ns[0] * ms[0] + ns[1] * ms[1] + ns[2] * ms[2] - 1) % beeg)


def power(b, n):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % MOD
		b = b * b % MOD
		n //= 2
	return s

def Inv(x):
	return power(x, MOD - 2)
MOD = 1000000007
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list()
	b = list()
	a1 = [2, 1, -1, -2, -1, 1]
	a2 = [-1, 1, 2, 1, -1, -2]
	a3 = [-1, -2, -1, 1, 2, 1]
	b1 = [2, 1, -1, -2, -1, 1]
	b2 = [-1, 1, 2, 1, -1, -2]
	b3 = [-1, -2, -1, 1, 2, 1]
	x1 = (a1[n % 6] + power(2, n)) * Inv(3) % MOD
	x2 = (a2[n % 6] + power(2, n)) * Inv(3) % MOD
	x3 = (a3[n % 6] + power(2, n)) * Inv(3) % MOD
	y1 = (b1[m % 6] + power(2, m)) * Inv(3) % MOD
	y2 = (b2[m % 6] + power(2, m)) * Inv(3) % MOD
	y3 = (b3[m % 6] + power(2, m)) * Inv(3) % MOD
	a.extend([x1, x2, x3])
	b.extend([y1, y2, y3])
	print(((a[0] * b[0] + a[1] * b[1] + a[2] * b[2]) % MOD + MOD - 1) % MOD)


import math
mod = 10 ** 9 + 7

def pow(b, n):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % mod
		b = b * b % mod
		n //= 2
	return s

def fun(x):
	return pow(x, mod - 2)
t = int(input())
while t:
	ans = 0
	a = [0, 0, 0]
	b = [0, 0, 0]
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	a[0] = ([2, 1, -1, -2, -1, 1][n % 6] + pow(2, n)) * fun(3) % mod
	a[1] = ([-1, 1, 2, 1, -1, -2][n % 6] + pow(2, n)) * fun(3) % mod
	a[2] = ([-1, -2, -1, 1, 2, 1][n % 6] + pow(2, n)) * fun(3) % mod
	b[0] = ([2, 1, -1, -2, -1, 1][m % 6] + pow(2, m)) * fun(3) % mod
	b[1] = ([-1, 1, 2, 1, -1, -2][m % 6] + pow(2, m)) * fun(3) % mod
	b[2] = ([-1, -2, -1, 1, 2, 1][m % 6] + pow(2, m)) * fun(3) % mod
	ans = ((a[0] * b[0] + a[1] * b[1] + a[2] * b[2]) % mod + mod - 1) % mod
	print(ans)
	t -= 1


import math
import cmath
p = pow(10, 9) + 7

def power(base, exp):
	if exp == 0:
		return 1
	temp = power(base, exp // 2)
	if exp % 2 == 0:
		return temp * temp % p
	else:
		return base * temp * temp % p

def power1(base, exp):
	if exp == 0:
		return 1
	temp = power1(base, exp // 2)
	if exp % 2 == 0:
		return temp * temp
	else:
		return base * temp * temp
t = int(input())
while t > 0:
	st = list(map(int, input().split()))
	pie = math.pi
	w = complex(math.cos(2 * pie / 3), math.sin(2 * pie / 3))
	s = 0
	k1 = int(power(2, st[0]))
	m1 = power1(-w ** 2, st[0])
	s += (k1 + round((w * m1 + w ** 2 * power1(-w, st[0])).real)) % p * (power(2, st[1]) + round((w * power1(-w ** 2, st[1]) + w ** 2 * power1(-w, st[1])).real)) % p * 333333336 ** 2 % p
	s += (k1 + round((w ** 2 * m1 + w ** 4 * power1(-w, st[0])).real)) % p * 333333336 ** 2 * (power(2, st[1]) + round((w ** 2 * power1(-w ** 2, st[1]) + w ** 4 * power1(-w, st[1])).real)) % p % p
	s += (k1 + round((m1 + power1(-w, st[0])).real)) % p * (power(2, st[1]) + round((power1(-w ** 2, st[1]) + power1(-w, st[1])).real)) % p * 333333336 ** 2 % p
	print((s - 1) % p)
	t -= 1


import math
MODULE = 10 ** 9 + 7
difs = ((1, 0, 0), (1, 1, 0), (0, 1, 0), (0, 1, 1), (0, 0, 1), (1, 0, 1))
for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	sm = [(pow(2, M, MODULE) - sum(difs[M % 6])) * pow(3, -1, MODULE) % MODULE + difs[M % 6][i] for i in range(3)]
	sn = [(pow(2, N, MODULE) - sum(difs[N % 6])) * pow(3, -1, MODULE) % MODULE + difs[N % 6][i] for i in range(3)]
	print((sum([sm[i] * sn[i] for i in range(3)]) - 1) % MODULE)


mod = 10 ** 9 + 7
inverse = 333333336

def get_power_1(N):
	if N == 0:
		return 1
	if N == 1:
		return 2
	ans = get_power_1(N // 2) % 3
	ans = ans * ans % 3
	if N % 2 == 1:
		ans = ans * 2 % 3
	return ans

def get_power_2(N):
	if N == 0:
		return 1
	if N == 1:
		return 2
	ans = get_power_2(N // 2) % mod
	ans = ans * ans % mod
	if N % 2 == 1:
		ans = ans * 2 % mod
	return ans

def get_terms(N):
	ans_1 = get_power_1(N)
	ans_2 = get_power_2(N)
	if ans_1 % 3 == 2:
		x0 = (ans_2 + 1) % mod * inverse % mod
		x1 = x0
		x2 = (x0 - 1 + mod) % mod
	elif ans_1 % 3 == 1:
		x0 = (ans_2 + mod - 1) % mod * inverse % mod
		x1 = x0
		x2 = (x0 + 1) % mod
	if N % 3 == 0:
		return (x2, x1, x0)
	if N % 3 == 1:
		return (x0, x1, x2)
	return (x0, x2, x1)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	n_terms = get_terms(n)
	m_terms = get_terms(m)
	ans = (n_terms[0] % mod * m_terms[0] % mod % mod + n_terms[1] % mod * m_terms[1] % mod % mod + n_terms[2] % mod * m_terms[2] % mod % mod) % mod
	print((ans - 1 + mod) % mod)


mod = 10 ** 9 + 7

def get_power(base, N):
	ans = 1
	if N == 0:
		return 1
	if N == 1:
		return base
	ans = get_power(base, N // 2) % mod
	ans = ans * ans % mod
	if N % 2 == 1:
		ans = ans * base % mod
	return ans

def bcl(g):
	return get_power(g, mod - 2)

def solution(n, m):
	coeff = [[2, 1, -1, -2, -1, 1], [-1, 1, 2, 1, -1, -2], [-1, -2, -1, 1, 2, 1]]
	two_n = get_power(2, n)
	two_m = get_power(2, m)
	bcl_3 = bcl(3) % mod
	arr_1 = [(coeff[0][n % 6] + two_n) * bcl_3, (coeff[1][n % 6] + two_n) * bcl_3, (coeff[2][n % 6] + two_n) * bcl_3]
	arr_2 = [(coeff[0][m % 6] + two_m) * bcl_3, (coeff[1][m % 6] + two_m) * bcl_3, (coeff[2][m % 6] + two_m) * bcl_3]
	ans = ((arr_1[0] * arr_2[0] + arr_1[1] * arr_2[1] + arr_1[2] * arr_2[2]) % mod + mod - 1) % mod
	return ans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(solution(n, m))


z = 1000000007
for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	a2 = [-1, 1, 2, 1, -1, -2]
	a3 = [-1, -2, -1, 1, 2, 1]
	b1 = [2, 1, -1, -2, -1, 1]
	a1 = [2, 1, -1, -2, -1, 1]
	b2 = [-1, 1, 2, 1, -1, -2]
	b3 = [-1, -2, -1, 1, 2, 1]
	kn0 = (a1[n % 6] + pow(2, n, z)) * pow(3, z - 2, z) % z
	km0 = (b1[m % 6] + pow(2, m, z)) * pow(3, z - 2, z) % z
	km2 = (b3[m % 6] + pow(2, m, z)) * pow(3, z - 2, z) % z
	kn1 = (a2[n % 6] + pow(2, n, z)) * pow(3, z - 2, z) % z
	km1 = (b2[m % 6] + pow(2, m, z)) * pow(3, z - 2, z) % z
	kn2 = (a3[n % 6] + pow(2, n, z)) * pow(3, z - 2, z) % z
	ans = kn0 * km0 + kn1 * km1 + km2 * kn2
	ans -= 1
	print(ans % z)


z = 1000000007

def po(a, b):
	ze = 1000000007
	k = 1
	b1 = b
	while b1 > 0:
		if b1 % 2 == 1:
			k = k * a % ze
		a = a * a % ze
		b1 >>= 1
	return k
for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	a2 = [-1, 1, 2, 1, -1, -2]
	a3 = [-1, -2, -1, 1, 2, 1]
	b1 = [2, 1, -1, -2, -1, 1]
	a1 = [2, 1, -1, -2, -1, 1]
	b2 = [-1, 1, 2, 1, -1, -2]
	b3 = [-1, -2, -1, 1, 2, 1]
	kn0 = (a1[n % 6] + po(2, n)) * po(3, z - 2) % z
	km0 = (b1[m % 6] + po(2, m)) * po(3, z - 2) % z
	km2 = (b3[m % 6] + po(2, m)) * po(3, z - 2) % z
	kn1 = (a2[n % 6] + po(2, n)) * po(3, z - 2) % z
	km1 = (b2[m % 6] + po(2, m)) * po(3, z - 2) % z
	kn2 = (a3[n % 6] + po(2, n)) * po(3, z - 2) % z
	ans = kn0 * km0 + kn1 * km1 + km2 * kn2
	ans = (ans % z + z - 1) % z
	print(ans % z)


from cmath import pi
from math import cos
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = 10 ** 9 + 7
	n2 = pow(2, n, d)
	m2 = pow(2, m, d)
	var = pow(9, d - 2, d)
	s1 = (n2 + round(2 * cos(n * pi / 3))) % d * ((m2 + round(2 * cos(m * pi / 3))) % d) % d
	s1 *= var
	s2 = (n2 - round(2 * cos((n + 1) * pi / 3))) % d * ((m2 - round(2 * cos((m + 1) * pi / 3))) % d) % d
	s2 *= var
	s3 = (n2 - round(2 * cos((n - 1) * pi / 3))) % d * ((m2 - round(2 * cos((m - 1) * pi / 3))) % d) % d
	s3 *= var
	print(int(round(s1 + s2 + s3) - 1) % d)


try:
	t = int(input())
	MOD = 1000000007
	while t:
		(n, m) = map(int, input().split())

		def power(x, y, Q):
			res = 1
			while y > 0:
				if y & 1 != 0:
					res = res * x % Q
				y = y >> 1
				x = x * x % Q
			return res % Q
		ans = 0
		if abs(n - m) % 6 == 1 or abs(n - m) % 6 == 5:
			ans = (power(2, n + m, 3 * MOD) + 1) // 3
		if abs(n - m) % 6 == 2 or abs(n - m) % 6 == 4:
			ans = (power(2, n + m, 3 * MOD) - 1) // 3
		if abs(n - m) % 6 == 3:
			ans = (power(2, n + m, 3 * MOD) - 2) // 3
		if abs(n - m) % 6 == 0:
			ans = (power(2, n + m, 3 * MOD) + 2) // 3
		print((ans - 1) % MOD)
		t = t - 1
except:
	pass


def pow2(n):
	ans = 1
	x = 2
	mod = 1000000007 * 3
	while n > 0:
		if n % 2 != 0:
			ans = ans * x % mod
		x = x * x % mod
		n = n >> 1
	return ans

def cos2(n):
	if n % 6 == 0:
		return 2
	elif n % 6 == 1:
		return 1
	elif n % 6 == 2:
		return -1
	elif n % 6 == 3:
		return -2
	elif n % 6 == 4:
		return -1
	else:
		return 1
t = int(input())
while t > 0:
	(n, m) = [int(i) for i in input().split()]
	n2 = pow2(n)
	m2 = pow2(m)
	ans = (n2 + cos2(n)) // 3 * ((m2 + cos2(m)) // 3) + (n2 + cos2(n + 2)) // 3 * ((m2 + cos2(m + 2)) // 3) + (n2 + cos2(n + 4)) // 3 * ((m2 + cos2(m + 4)) // 3) - 1
	ans = ans % 1000000007
	print(ans)
	t -= 1


MOD = 10 ** 9 + 7
INV3 = 333333336

def modpow(base, exp, mod):
	result = 1
	while exp:
		if exp & 1:
			result = result * base % mod
		base = base * base % mod
		exp >>= 1
	return result

def main(N, M):
	return (modpow(2, N + M, MOD) - [1, 2, 4, 5, 4, 2][(M - N) % 6]) * INV3 % MOD
T = int(input().strip())
for _ in range(T):
	(N, M) = [int(x) for x in input().strip().split()[:2]]
	(N, M) = (min(N, M), max(N, M))
	print(main(N, M))


import math

def quick_poly(n):
	type = [[1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [0, 0, 1], [1, 0, 1]]
	mod = 1000000007
	sum_p = pow(2, n, 3 * mod)
	base = int((sum_p - sum_p % 3) / 3)
	array = type[n % 6]
	array[0] = int((array[0] + base) % mod)
	array[1] = int((array[1] + base) % mod)
	array[2] = int((array[2] + base) % mod)
	return array

def count(n, m):
	mod = 10 ** 9 + 7
	nside = quick_poly(n)
	mside = quick_poly(m)
	count = 0
	count = nside[0] * mside[0] % mod + nside[1] * mside[1] % mod + nside[2] * mside[2] % mod
	return (count - 1) % mod
n = int(input())
for _ in range(0, n):
	array = list(map(int, input().split()))
	print(count(array[0], array[1]))


import math

def power(x, y, p):
	ans = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % p
		y = y >> 1
		x = x * x % p
	return ans
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	divide = 10 ** 9 + 7
	a = power(2, n, divide)
	b = power(2, m, divide)
	n1 = (a + round(2 * math.cos(n * math.pi / 3))) % divide
	n2 = (a - round(2 * math.cos((n - 1) * math.pi / 3))) % divide
	n3 = (a - round(2 * math.cos((n + 1) * math.pi / 3))) % divide
	m1 = (b + round(2 * math.cos(m * math.pi / 3))) % divide
	m2 = (b - round(2 * math.cos((m - 1) * math.pi / 3))) % divide
	m3 = (b - round(2 * math.cos((m + 1) * math.pi / 3))) % divide
	x = (n1 * m1 + n2 * m2 + n3 * m3) % divide
	y = x * power(9, divide - 2, divide)
	z = y - 1
	ans = z % divide
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	n1 = n
	n2 = m
	nz = 1
	mz = 1
	p1 = 2
	p2 = 2
	while n1:
		if n1 % 2:
			nz = nz * p1 % 1000000007
		p1 = p1 * p1 % 1000000007
		n1 //= 2
	while n2:
		if n2 % 2:
			mz = mz * p2 % 1000000007
		p2 = p2 * p2 % 1000000007
		n2 //= 2
	l = [-1, 1, 2, 1, -1, -2]
	ans = (l[m % 6] + mz) * 333333336 * ((l[n % 6] + nz) * 333333336) + (l[(m + 4) % 6] + mz) * 333333336 * ((l[(n + 4) % 6] + nz) * 333333336) + (l[(n + 2) % 6] + nz) * 333333336 * ((l[(m + 2) % 6] + mz) * 333333336) - 1
	print(ans % 1000000007)


inf = 1000000007

def an(n, a):
	z = 1
	while n:
		if n % 2:
			z = z * a % inf
		a = a * a % inf
		n //= 2
	return z
l1 = [2, 1, -1, -2, -1, 1]

def i0(n, a):
	return (l1[n % 6] + a) * 333333336 % inf

def i1(n, a):
	m = n % 6 + 4
	return (l1[m % 6] + a) * 333333336 % inf

def i2(n, a):
	m = n % 6 + 2
	return (l1[m % 6] + a) * 333333336 % inf
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = an(n, 2)
	b = an(m, 2)
	print((i0(n, a) * i0(m, b) + i1(n, a) * i1(m, b) + i2(n, a) * i2(m, b) - 1) % inf)


T = int(input())
B = 3 * (pow(10, 9) + 7)
for i in range(T):
	I = input().split()
	(N, M) = tuple([int(j) for j in I])
	if (N - M) % 3 == 0:
		if (N + M) % 2 == 0:
			print((pow(2, N + M, B) + 2) // 3 - 1)
		else:
			print((pow(2, N + M, B) - 2) % B // 3 - 1)
	elif (N + M) % 2 == 0:
		print((pow(2, N + M, B) - 1) // 3 - 1)
	else:
		print((pow(2, N + M, B) + 1) // 3 - 1)


for _ in range(int(input())):
	(sa, me) = list(map(int, input().split()))
	(er, hi) = [[[2, 1, -1, -2, -1, 1][sa % 6] + pow(2, sa, 1000000007), [-1, 1, 2, 1, -1, -2][sa % 6] + pow(2, sa, 1000000007), [-1, -2, -1, 1, 2, 1][sa % 6] + pow(2, sa, 1000000007)], [[2, 1, -1, -2, -1, 1][me % 6] + pow(2, me, 1000000007), [-1, 1, 2, 1, -1, -2][me % 6] + pow(2, me, 1000000007), [-1, -2, -1, 1, 2, 1][me % 6] + pow(2, me, 1000000007)]]
	print(((er[0] * hi[0] + er[1] * hi[1] + er[2] * hi[2]) * 111111112 + 1000000006) % 1000000007)


mod = int(1000000000.0 + 7)

def newIdentity(n):
	m = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
	return m
temp = newIdentity(3)

def matmul(c, a, b):
	for i in range(3):
		for j in range(3):
			temp[i][j] = 0
			for k in range(3):
				temp[i][j] += a[i][k] * b[k][j]
			temp[i][j] %= mod
	for i in range(3):
		for j in range(3):
			c[i][j] = temp[i][j]

def power(x, y):
	a = newIdentity(3)
	while y:
		if y & 1:
			matmul(a, a, x)
		matmul(x, x, x)
		y >>= 1
	return a
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	print((power([[0 if i == j else 1 for j in range(3)] for i in range(3)], n + m)[0][(n + m + m) % 3] - 1) % mod)


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())
rem = 1000000007
inv = power(3, rem - 2, rem)
for _ in range(t):
	(t, z) = map(int, input().split())
	if t % 3 == 0:
		tval0 = 2
		tval1 = -1
		tval2 = -1
	elif t % 3 == 1:
		tval0 = -1
		tval1 = -1
		tval2 = 2
	else:
		tval0 = -1
		tval1 = 2
		tval2 = -1
	if z % 3 == 0:
		zval0 = 2
		zval1 = -1
		zval2 = -1
	elif z % 3 == 1:
		zval0 = -1
		zval1 = -1
		zval2 = 2
	else:
		zval0 = -1
		zval1 = 2
		zval2 = -1
	if t % 2 == 1:
		tval0 *= -1
		tval1 *= -1
		tval2 *= -1
	if z % 2 == 1:
		zval0 *= -1
		zval1 *= -1
		zval2 *= -1
	p1 = power(2, t, rem)
	p2 = power(2, z, rem)
	t1 = (p1 + tval1) * inv % rem
	t2 = (p1 + tval2) * inv % rem
	t0 = (p1 + tval0) * inv % rem
	z0 = (p2 + zval0) * inv % rem
	z1 = (p2 + zval1) * inv % rem
	z2 = (p2 + zval2) * inv % rem
	a = t0 * z0
	b = t1 * z1
	c = t2 * z2
	print((a + b + c - 1) % rem)


from itertools import product
diff = [2, 1, -1, -2, -1, 1]
output = []
inverse_3 = pow(3, -1, 10 ** 9 + 7)
for _ in range(int(input())):
	(N, M) = map(int, input().split(' '))
	output.append((pow(2, N + M, 10 ** 9 + 7) + diff[(N - M) % 6]) * inverse_3 % (10 ** 9 + 7) - 1)
print('\n'.join(map(str, output)))


for p in range(int(input())):
	(q, r) = list(map(int, input().split()))
	(g, h) = [[[2, 1, -1, -2, -1, 1][q % 6] + pow(2, q, 1000000007), [-1, 1, 2, 1, -1, -2][q % 6] + pow(2, q, 1000000007), [-1, -2, -1, 1, 2, 1][q % 6] + pow(2, q, 1000000007)], [[2, 1, -1, -2, -1, 1][r % 6] + pow(2, r, 1000000007), [-1, 1, 2, 1, -1, -2][r % 6] + pow(2, r, 1000000007), [-1, -2, -1, 1, 2, 1][r % 6] + pow(2, r, 1000000007)]]
	print(((g[0] * h[0] + g[1] * h[1] + g[2] * h[2]) * 111111112 + 1000000006) % 1000000007)


T = int(input())
p = int(1000000000.0 + 7)
for i in range(T):
	s = input()
	a = s.split()
	(N, M) = (int(a[0]), int(a[1]))
	(a, b) = (pow(2, N, 3 * p), pow(2, M, 3 * p))
	(x, y) = ((-1) ** N, (-1) ** M)
	if M % 3 == N % 3:
		print(((a * b + 2 * x * y) // 3 - 1) % p)
	else:
		print(((a * b - x * y) // 3 - 1) % p)


def cos6(n):
	if n % 6 == 0:
		return 2
	if n % 6 == 1:
		return 1
	if n % 6 == 2:
		return -1
	if n % 6 == 3:
		return -2
	if n % 6 == 4:
		return -1
	if n % 6 == 5:
		return 1
mod = 1000000007
inv3 = 333333336

def b3(n, f):
	return (pow(2, n, mod) + cos6(n + f)) * inv3 % mod
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	print((b3(m, 0) * b3(n, 0) + b3(n, 2) * b3(m, 2) + b3(n, -2) * b3(m, -2) - 1) % mod)


t = int(input())
s = [1, 2, 4, 5, 4, 2]
k = 1000000007
for i in range(t):
	(n, m) = [int(a) for a in input().split()]
	num = (pow(2, m + n, k) - s[(m - n) % 6]) * 333333336 % k
	print(num)


s = [1, 2, 1, 2, 1, 2]
mod = 10 ** 9 + 7
s1 = [[1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [0, 0, 1], [1, 0, 1]]

def inv(x):
	return pow(x, mod - 2, mod)

def add(a, b):
	return [a[0] + b[0], a[1] + b[1], a[2] + b[2]]

def gen(n):
	if n % 2 == 0:
		x = 1
	else:
		x = 2
	num = pow(2, n, mod) - x
	num = num * inv(3)
	num = num % mod
	l = [num, num, num]
	return add(l, s1[n % 6])
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l1 = gen(n)
	l2 = gen(m)
	ans = l1[0] * l2[0] + l1[1] * l2[1] + l1[2] * l2[2]
	ans = ans % mod
	ans = ans - 1
	print(ans % mod)