Manasa is a student in the department of Mathematics. She is pretty good at doing calculations involving small numbers, but large numbers scare her. So she wants you to help her in the following calculations.

Given two numbers in the following manner:

$A=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times\text{...}\times p_N^{a_N}$
$B=p_1^{b_1}\times p_2^{b_2}\times p_3^{b_3}\times\text{...}\times p_N^{b_N}$

($p_i$ is a prime number, and all the $p_i$'s are distinct)

She wants you to calculate ${S}$ for her, where ${S}$ is the sum of $m+n$ for all pairs of numbers  where $m\leq n$, $\text{gcd}(m,n)=B$ and $\text{lcm}(m,n)=A$. In other words:

$S=\sum_{\begin{equation}\begin{aligned}gcd(m,n)=B\\ \text{lcm}(m,n)=A\\ m\leq n}}(m+n)$ 

As the value of ${S}$ can be very large, she wants you to print $S\:\text{mod}\:10^9+7$.

Input Format 

The first line contains an integer $N$, the number of prime factors. 

Each of the next $N$ lines contains three numbers: $p_i$, $b_i$ and $a_i$.

Output Format 

Print the value of $S\:\text{mod}\:10^9+7$.

Constraints  

$1\leq N\leq500$ 

$2\leq p_i\leq5000$ 

$1\leq a_i\leq10^9$ 

$1\leq b_i\leq10^9$ 

$b_i\leq a_i$  

Sample Input

2
2 1 2 
3 1 2

Sample Output

72

Explanation

We have $B=6$ and $A=36$. There are two pairs of integers $(m,n)$ with ${gcd}$ equal to ${6}$ and ${lcm}$ equal to $36$, and such that $m\leq n$. These are $(12,18)$ and $(6,36)$:

$\text{gcd}(12,18)=6$ and $\text{lcm}(12,18)=36$  
$\text{gcd}(6,36)=6$ and $\text{lcm}(6,36)=36$  

Hence, $S=(12+18)+(6+36)=72$

Source: hackerrank | Difficulty: MEDIUM
Tags: Matrices


Solutions:
P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


import sys
from math import sqrt

def solve():
	stdin = sys.stdin
	write = sys.stdout.write
	N = int(stdin.readline())
	ans = 1
	MOD = 10 ** 9 + 7
	same = True
	for _ in range(N):
		(p, a, b) = map(int, stdin.readline().split())
		if a != b:
			same = False
			ans = ans * (pow(p, a, MOD) + pow(p, b, MOD)) % MOD
		else:
			ans = ans * pow(p, a, MOD) % MOD
	if same:
		ans = ans * 2 % MOD
	write('%d\n' % ans)
solve()


LARGE_MOD = 10 ** 9 + 7

def quick_power(x, e, mod):
	exponent = e
	current_power_of_x = x
	result = 1
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * current_power_of_x
			result = result % mod
		exponent = exponent // 2
		current_power_of_x = current_power_of_x * current_power_of_x
		current_power_of_x = current_power_of_x % mod
	return result
num_test_cases = int(input())
result = 1
all_equal_so_far = True
for c in range(num_test_cases):
	line = input().split()
	p = int(line[0])
	a = int(line[1])
	b = int(line[2])
	if a == b:
		result *= quick_power(p, a, LARGE_MOD)
	else:
		all_equal_so_far = False
		result *= quick_power(p, a, LARGE_MOD) + quick_power(p, b, LARGE_MOD)
	result = result % LARGE_MOD
if all_equal_so_far:
	result *= 2
	result = result % LARGE_MOD
print(result)


import math
X = 1000000007
N = int(input())
res = 1
f = 0
for i in range(N):
	(p, a, b) = list(map(int, input().split()))
	if a == b:
		res = res * pow(p, a, X) % X
	else:
		f = 1
		res = res * (pow(p, a, X) + pow(p, b, X)) % X
if f == 0:
	res = res * 2 % X
print(res)


n = int(input())
mod = 1000000007
primes = []
first = dict()
second = dict()

def solve(pos):
	if pos == n:
		return 1
	if first[primes[pos]] == second[primes[pos]]:
		return pow(primes[pos], first[primes[pos]], mod) * solve(pos + 1) % mod
	return (pow(primes[pos], first[primes[pos]], mod) + pow(primes[pos], second[primes[pos]], mod)) * solve(pos + 1) % mod
for i in range(0, n):
	ip = input().split(' ')
	p = int(ip[0])
	a = int(ip[1])
	b = int(ip[2])
	primes.append(p)
	first[p] = a
	second[p] = b
if first == second:
	ans = 2
	for i in primes:
		ans = ans * pow(i, first[i], mod) % mod
	print(ans)
else:
	print(solve(0))


MOD = 10 ** 9 + 7
N = int(input())
P = {}
for _ in range(N):
	(p, b, a) = (int(_) for _ in input().split())
	P[p] = (b, a)
(s, c) = (1, 0)
for p in P:
	if P[p][0] == P[p][1]:
		s *= pow(p, P[p][0], MOD)
		c += 1
	else:
		s *= pow(p, P[p][0], MOD) + pow(p, P[p][1], MOD)
	s %= MOD
if c < len(P):
	print(s)
else:
	print(2 * s % MOD)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from itertools import accumulate, combinations
from fractions import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
home = 0
lire = 0
trace = 0
if home:
	from mesures import ch
modo = 10 ** 9 + 7

def faire4(pars):
	(A, B, fs) = (1, 1, [])
	for (p, b, a) in pars:
		B *= pow(p, b, modo)
		if a != b:
			fs += [pow(p, a - b, modo)]
	res = B
	if len(fs) == 0:
		return 2 * B % modo
	for lc in fs:
		res = res * (1 + lc) % modo
	return res % modo
pars = []
if home and (not lire):
	pass
else:
	nbnb = int(input().strip())
	for _ in range(nbnb):
		(p, b, a) = map(int, input().strip().split())
		pars += [[p, b, a]]
if home:
	pass
else:
	print(faire4(pars))


mm = 10 ** 9 + 7

def pow_mod(a, n):
	ret = 1
	while n > 0:
		if n & 1 == 1:
			ret = ret * a % mm
		a = a * a % mm
		n >>= 1
	return ret
n = int(input())
ret = 1
is_equal = True
for i in range(n):
	(p, b, a) = [int(x) for x in input().split()]
	ret = ret * pow_mod(p, b) % mm
	if a > b:
		is_equal = False
		ret = ret * (pow_mod(p, a - b) + 1) % mm
if is_equal:
	ret = 2 * ret % mm
print(ret)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total
N = int(input())
prime_power_list = []
for i in range(0, N):
	pab = [int(a) for a in input().split()]
	prime_power_list.append(pab)
modulus = pow(10, 9) + 7
total_product = 1
all_are_equal = True
for i in range(0, N):
	if prime_power_list[i][1] == prime_power_list[i][2]:
		prod_i = pow_mod(prime_power_list[i][0], prime_power_list[i][1], modulus)
	else:
		all_are_equal = False
		prod_i = pow_mod(prime_power_list[i][0], prime_power_list[i][1], modulus) + pow_mod(prime_power_list[i][0], prime_power_list[i][2], modulus)
	total_product *= prod_i
	total_product %= modulus
if all_are_equal:
	total_product *= 2
	total_product %= modulus
print(total_product)


import sys

def solve(uu, m):
	total = 1
	for (i, (p, b, a)) in enumerate(uu):
		if a == b:
			delta = pow(p, a, m)
		else:
			delta = pow(p, b, m) + pow(p, a, m)
			delta %= m
		total *= delta
		total %= m
		print('i=%d p=%d b=%d a=%d delta=%d total=%d' % (i, p, b, a, delta, total), file=sys.stderr)
	(match, prod) = (True, 1)
	for (p, b, a) in uu:
		if a != b:
			match = False
			break
		prod *= pow(p, a, m)
		prod %= m
	if match:
		total = prod * 2 % m
	return total
n = int(input())
uu = list()
for _ in range(n):
	(p, b, a) = map(int, input().split())
	uu.append((p, b, a))
m = pow(10, 9) + 7
print(solve(uu, m))


s = 1
m = 1000000007
isAllSame = True
N = int(input())
for _ in range(N):
	[pi, bi, ai] = input().split()
	[pi, bi, ai] = [int(pi), int(bi), int(ai)]
	if bi == ai:
		s = s * pow(pi, bi, m) % m
	else:
		isAllSame = False
		s = s * (pow(pi, bi, m) + pow(pi, ai, m)) % m
if isAllSame:
	print(s * 2 % m)
else:
	print(s)


P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


mm = 10 ** 9 + 7
n = int(input())
ar = {}
for _ in range(n):
	(p, b, a) = (int(_) for _ in input().split())
	ar[p] = (b, a)
(x, c) = (1, 0)
for p in ar:
	if ar[p][0] == ar[p][1]:
		x *= pow(p, ar[p][0], mm)
		c += 1
	else:
		x *= pow(p, ar[p][0], mm) + pow(p, ar[p][1], mm)
	x %= mm
if c < len(ar):
	print(x)
else:
	print(2 * x % mm)


mod = pow(10, 9) + 7
n = int(input())
r = 1
g = 1
for i in range(n):
	(p, b, a) = list(map(int, input().split()))
	g = g * pow(p, b, mod) % mod
	if a > b:
		r = r * (1 + pow(p, a - b, mod)) % mod
if r == 1:
	r = 2
r = g * r % mod
print(r)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total
N = int(input())
prime_power_list = []
for i in range(0, N):
	pab = [int(a) for a in input().split()]
	prime_power_list.append(pab)
modulus = pow(10, 9) + 7
total_product = 1
all_are_equal = True
for i in range(0, N):
	if prime_power_list[i][1] == prime_power_list[i][2]:
		prod_i = pow_mod(prime_power_list[i][0], prime_power_list[i][1], modulus)
	else:
		all_are_equal = False
		prod_i = pow_mod(prime_power_list[i][0], prime_power_list[i][1], modulus) + pow_mod(prime_power_list[i][0], prime_power_list[i][2], modulus)
	total_product *= prod_i
	total_product %= modulus
if all_are_equal:
	total_product *= 2
	total_product %= modulus
print(total_product)


import math
ma = 10 ** 9 + 7
ab = ba = 1
for x in range(int(input())):
	(p, a, b) = map(int, input().strip().split())
	if a == b:
		ba *= pow(p, a, ma) % ma
	else:
		ba *= (pow(p, a, ma) + pow(p, b, ma)) % ma
		ab = 0
print(ba * (1 + ab) % ma)


MOD = 10 ** 9 + 7
N = int(input())
P = [map(int, input().split()) for _ in range(N)]
S = 1
a_eq_b = True
for (p, a, b) in P:
	if a != b:
		S *= pow(p, a, MOD) + pow(p, b, MOD)
		a_eq_b = False
	else:
		S *= pow(p, a, MOD)
	S %= MOD
if a_eq_b:
	S = (S + S) % MOD
print(S)


import io
import math
import os
import sys
MOD = 1000000007

def read_case(ifile=sys.stdin):
	n = int(ifile.readline())
	pab = [[int(s) for s in ifile.readline().split()] for k in range(n)]
	return (n, pab)

def compute_mn_sum(n, pab):
	result = 1
	multiplier = 2
	for (p, a, b) in pab:
		pa = pow(p, a, MOD)
		if a < b:
			pb = pow(p, b, MOD)
			multiplier = 1
		else:
			pb = 0
		result = result * (pa + pb) % MOD
	return result * multiplier % MOD
case_s0 = '2\n2 1 2 \n3 1 2'

def test():
	print('MOD =', MOD)
	(n, pab) = read_case(io.StringIO(case_s0))
	result = compute_mn_sum(n, pab)
	print(n, *pab)
	print(result)
	print(compute_mn_sum(2, ((2, 1, 1), (3, 2, 2))))
(n, pab) = read_case()
result = compute_mn_sum(n, pab)
print(result)


n = int(input())
modulus = 10 ** 9 + 7
base = 1
answer_prod = 1
bad_answer = False
for _ in range(n):
	this_entry = [int(x) for x in input().split()]
	pi = this_entry[0]
	bi = this_entry[1]
	ai = this_entry[2]
	base *= pow(pi, bi, modulus)
	if ai > bi:
		answer_prod *= pow(pi, ai - bi, modulus) + 1
if not bad_answer and answer_prod != 1:
	print(base * answer_prod % modulus)
else:
	print(base * 2 % modulus)


def power(a, b, mod):
	if b == 0:
		return 1
	res = power(a, b // 2, mod)
	if b % 2 == 0:
		return res * res % mod
	return a * (res * res) % mod % mod
mod = int(10 ** 9 + 7)
res = 1
N = int(input())
dist = False
for i in range(N):
	vals = str(input()).split(' ')
	p = int(vals[0])
	b = int(vals[1])
	a = int(vals[2])
	numer = 1
	if a == b:
		numer = power(p, a, mod)
	else:
		dist = True
		numer = power(p, a, mod) + power(p, b, mod)
	res = res * numer % mod
if not dist:
	res = res * 2 % mod
print(res)


v = pow(10, 9) + 7
gcd = 1
ans = 1
n = int(input())
flag = 0
for _ in range(n):
	inp = list(map(int, input().split()))
	p = inp[0]
	a = inp[1]
	b = inp[2]
	gcd *= pow(p, min(a, b), v)
	gcd = gcd % v
	if a != b:
		flag = 1
		ans *= 1 + pow(p, abs(a - b), v)
	ans = ans % v
if flag == 0:
	print(2 * gcd % v)
else:
	print(ans * gcd % v)


modulo_constant = 10 ** 9 + 7

def gcd_lcm_sum(pbal):
	ret = 1
	double = 2
	for (p, b, a) in pbal:
		if a == b:
			ret *= pow(p, a, modulo_constant)
		else:
			ret *= pow(p, a, modulo_constant) + pow(p, b, modulo_constant)
			double = 1
		ret %= modulo_constant
	return ret * double % modulo_constant

def run_gcd_lcm_sum(reader=input, printer=print):
	printer(gcd_lcm_sum([[int(x) for x in reader().split()] for _ in range(int(reader()))]))
run_gcd_lcm_sum()


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


MOD = 10 ** 9 + 7
s = 1
delta = False
for _ in range(int(input())):
	(p, g, l) = map(int, input().split())
	s *= pow(p, g, MOD)
	if l > g:
		s *= 1 + pow(p, l - g, MOD)
		delta = True
	s %= MOD
print(s if delta else 2 * s % MOD)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


P = 10 ** 9 + 7
n = int(input())
data = [map(int, input().split()) for _ in range(n)]
ret = 1
allEq = True
for (p, a, b) in data:
	if a == b:
		ret *= pow(p, a, P)
	else:
		allEq = False
		ret *= (pow(p, a, P) + pow(p, b, P)) % P
	ret %= P
if allEq:
	ret = ret * 2 % P
print(ret)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


import math
n = int(input())
ans = 1
mod = int(1000000000.0 + 7)
flag = True
for i in range(n):
	(p, a, b) = list(map(int, input().rstrip().split(' ')))
	t = pow(p, b, mod)
	if a != b:
		flag = False
		t += pow(p, a, mod)
	ans = ans * t % mod
if flag:
	ans = ans * 2 % mod
print(ans)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


modulo = 10 ** 9 + 7
ret = 1
n = int(input().strip())
a_is_b = True
for _ in range(n):
	(p, b, a) = map(int, input().strip().split())
	if b != a:
		a_is_b = False
		ret = ret * (1 + pow(p, a - b, modulo)) % modulo
	ret = ret * pow(p, b, modulo) % modulo
if a_is_b:
	ret <<= 1
	if ret >= modulo:
		ret -= modulo
print(ret)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)


from functools import reduce
m = 1000000007

def mul_m(a, b):
	return a * b % m

def zpow(a, b, m):
	return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
	(p[i], b[i], a[i]) = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all((a[i] == b[i] for i in range(n))):
	print(B * 2 % m)
else:
	print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)