For a given integer $n$, there is a tower built from $3^{n}$ blocks stacked vertically. Each of these blocks can be colored in $3$ different colors: red, green or blue. How many different colorings of the tower can be created? Two colorings are considered different if and only if there exists at least one block with different colors in the colorings. Since the result can be a huge number, apply a modulo $10^9+7$ on the result.

Input Format

The first line contains a single integer $n$.  

Constraints

$1\leq n\leq10^9$

Output Format

In a single line print a single integer denoting the number of different colorings of tower of the height $3^{n}$ calculated modulo $10^9+7$.  

Sample Input 0
1

Sample Output 0
27

Explanation 0

In the sample we have $n=1$, so the tower has height $3^n=3$. Each of these three blocks can be colored with any of $3$ available colors, so the total number of different colorings is $3\times3\times3=27$.

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
import sys
import math

def power(p, z, b, c, q):
	cp = 0
	while q % p == 0:
		cp += 1
		q /= p
	t = q - 1
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, q)

def solve(a, b, c, q):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= power(p, z, b, c, q)
			result %= q
		p += 1
	if a != 1:
		result *= power(a, 1, b, c, q)
	return result % q

def towerColoring(n):
	return solve(3, 3, n, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
mod = 10 ** 9 + 7

def pmod(a, b, c):
	if b == 0:
		return 1
	k = pmod(a, b // 2, c)
	if b % 2 == 0:
		return k * k % c
	return k * k * a % c

def towerColoring(n):
	return pmod(3, pmod(3, n, mod - 1), mod)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 10 ** 9 + 6), 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 10 ** 9 + 6), 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
print(pow(3, pow(3, n, 1000000006), 1000000007))


import sys

def Pow(x, a, n):
	if a == 0:
		return 1
	r = Pow(x, a // 2, n)
	r = r * r
	return [r % n, r * x % n][a % 2]

def towerColoring(n):
	P = 10 ** 9 + 7
	a = Pow(3, n, P - 1)
	return Pow(3, a, P)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	z = pow(10, 9) + 7
	phi_z = z - 1
	towers = pow(3, n, phi_z)
	return pow(3, towers, z)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
MOD = 1000000007

def towerColoring(n):
	e = pow(3, n, MOD - 1)
	return pow(3, e, MOD)
n = int(input().strip())
result = towerColoring(n)
print(result)


Mod = 1000000007

def powm(a, n, m):
	r = 1
	while n > 0:
		if n & 1:
			r = r * a % m
		a = a * a % m
		n //= 2
	return r

def towerColoring(n):
	return powm(3, powm(3, n, Mod - 1), Mod)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
MOD = 10 ** 9 + 7

def pow3mod(n, mod):
	res = 1
	tmul = 3
	while n > 0:
		if n % 2 == 1:
			res = res * tmul % mod
		tmul = tmul * tmul % mod
		n //= 2
	return res

def towerColoring(n):
	pw = pow3mod(n, MOD - 1)
	return pow3mod(pw, MOD)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	res = pow(3, n, 10 ** 9 + 6)
	return pow(3, res, 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 10 ** 9 + 6), 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
MOD = 10 ** 9 + 7
PHI = MOD - 1
print(pow(3, pow(3, n, PHI), MOD))


import sys
from fractions import gcd
M = 10 ** 9 + 7
phiM = 1000000006

def towerColoring(n):
	return pow(3, pow(3, n, phiM), M)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
m = 10 ** 9 + 7

def towerColoring(n):
	return pow(3, pow(3, n, m - 1), m)
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
m = 10 ** 9 + 7
print(pow(3, pow(3, n, m - 1), m))


import sys
MODULO = 10 ** 9 + 7

def towerColoring(n):
	if n == 1:
		return 27
	phi = MODULO - 1
	temp = pow(3, n, phi)
	return pow(3, temp, MODULO)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
from math import sqrt
Q = 10 ** 9 + 7
F = 500000003

def factor(n):
	factors = [1, n]
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			factors.append(i)
			factors.append(n // i)
	return sorted(factors)

def towerColoring(n):
	return pow(3, pow(3, n, F), Q)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number

def towerColoring(n):
	p = pow_mod(3, n, 1000000006)
	return pow_mod(3, p, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	mod = 10 ** 9 + 7
	temp = pow(3, n, mod - 1)
	res = pow(3, temp, mod)
	return res
n = int(input().strip())
result = towerColoring(n)
print(result)


P = 10 ** 9 + 7
phiP = P - 1
n = int(input())
print(pow(3, pow(3, n, phiP), P))


import sys

def repeated_squaring(b, p, m):
	if p == 0:
		return 1
	if p == 1:
		return b
	if p % 2 == 0:
		return repeated_squaring(b * b % m, p // 2, m)
	return b * (repeated_squaring(b * b % m, p // 2, m) % m) % m

def towerColoring(n):
	ans = repeated_squaring(3, n, 1000000006)
	return repeated_squaring(3, ans, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


def pow(b, n, mod):
	if n == 1:
		return b
	(part_power, rest) = divmod(n, 2)
	part = pow(b, part_power, mod) % mod
	if rest == 0:
		return part * part % mod
	else:
		return part * part * b % mod

def towerColoring(n):
	h_mod = pow(3, n, int(1000000000.0 + 6))
	return pow(3, h_mod, int(1000000000.0 + 7))
n = int(input().strip())
result = towerColoring(n)
print(result)


MOD = 10 ** 9 + 7
print(pow(3, pow(3, int(input()), MOD - 1), MOD))


MOD = 10 ** 9 + 7
import sys

def towerColoring(n):
	return pow(3, pow(3, n, 500000003), MOD)
n = int(input().strip())
result = towerColoring(n)
print(result)


p = 10 ** 9 + 7
n = int(input())
b = pow(3, n, p - 1)
print(pow(3, b, p))


import sys
import math

def towerColoring(n):
	mod = 10 ** 9 + 7
	exp = pow(3, n, mod - 1)
	return pow(3, exp, mod)
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
P = 10 ** 9 + 7
r = pow(3, n, P - 1)
print(pow(3, r, P))


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 10 ** 9 + 6), 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


mod = 10 ** 9 + 7

def towerColoring(n):
	p = pow(3, n, mod - 1)
	return pow(3, p, mod)
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
print(pow(3, pow(3, n, 1000000006), 1000000007))


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 1000000006), 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	MOD1 = 10 ** 9 + 7
	MOD2 = 10 ** 9 + 6
	return pow(3, pow(3, n, MOD2), MOD1)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
order = 500000003

def towerColoring(n):
	rem = pow(3, n, order)
	return pow(3, rem, 7 + 10 ** 9)
n = int(input().strip())
result = towerColoring(n)
print(result)


modu = 10 ** 9 + 7
n = int(input().strip())
m = pow(3, n, modu - 1)
result = pow(3, m, modu)
print(result)


import sys

def towerColoring(n):
	mod = int(1000000000.0 + 7)
	pow_required = pow(3, n, mod - 1)
	res = pow(3, pow_required, mod)
	return res
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
M = 1000000007

def pow_3(n, Mod):
	if n == 0:
		return 1
	elif n == 1:
		return 3
	elif n % 2 == 0:
		k = pow_3(int(n / 2), Mod)
		result = k * k % Mod
	else:
		k = pow_3(int((n - 1) / 2), Mod)
		result = 3 * k * k % Mod
	return result

def towerColoring(n):
	B = pow_3(n, M - 1)
	res = pow_3(B, M)
	return res
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	modulus = 10 ** 9 + 7
	num_blocks = pow(3, n, modulus - 1)
	return pow(3, num_blocks, modulus)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def modular_pow(base, exponent, modulus):
	if modulus == 1:
		return 0
	result = 1
	base = base % modulus
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		exponent = exponent // 2
		base = base * base % modulus
	return result

def towerColoring(n):
	n = n % (5 * 10 ** 8 + 2)
	modulus = 10 ** 9 + 6
	n = modular_pow(3, n, modulus)
	modulus += 1
	n = modular_pow(3, n, modulus)
	return n
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
mymod = 7 + 10 ** 9

def rem(n, p):
	if n == 1:
		return 3 ** n % p
	if n % 2 == 0:
		return rem(n // 2, p) ** 2 % p
	else:
		return rem(n - 1, p) * 3 % p

def towerColoring(n):
	m = rem(n, mymod - 1)
	ans = rem(m, mymod)
	return ans
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
import math

def towerColoring(n):
	s = '{0:b}'.format(n)
	k = 3
	c = 1
	sn = len(s)
	for i in range(sn):
		if s[sn - i - 1] == '1':
			c = c * k % 1000000006
		k = k * k % 1000000006
	s = '{0:b}'.format(c)
	k = 3
	c = 1
	sn = len(s)
	for i in range(sn):
		if s[sn - i - 1] == '1':
			c = c * k % 1000000007
		k = k * k % 1000000007
	return c
n = int(input().strip())
result = towerColoring(n)
print(result)


MOD = 10 ** 9 + 7
n = int(input())
print(pow(3, pow(3, n, MOD - 1), MOD))


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 10 ** 9 + 6), 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	modulus = 10 ** 9 + 7
	miniMod = (modulus - 1) // 2
	intermediate = pow(3, n, miniMod)
	return pow(3, intermediate, modulus)
n = int(input().strip())
result = towerColoring(n)
print(result)


def fast(base, exp, sub):
	res = 1
	mod = 1000000007 - sub
	while exp > 0:
		if exp & 1:
			res = res * base % mod
		exp = exp >> 1
		base = base * base % mod
	return res
n = int(input())
pw = fast(3, n, 1)
print(fast(3, pw, 0))


import sys

def towerColoring(n):
	c = pow(3, n, 10 ** 9 + 6)
	return pow(3, c, 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
mod = 10 ** 9 + 7

def towerColoring(n):
	a = pow(3, n, mod - 1)
	return pow(3, a, mod)
n = int(input().strip())
result = towerColoring(n)
print(result)


def fast_pow(base, n, M):
	if n == 0:
		return 1
	if n == 1:
		return base
	half = fast_pow(base, n // 2, M)
	if n % 2 == 0:
		return half * half % M
	else:
		return half * half % M * base % M
n = int(input())
res = fast_pow(3, n, 1000000006)
t = fast_pow(3, res, 1000000007)
print(t)


import sys

def towerColoring(n):
	m = 10 ** 9 + 7
	return pow(3, pow(3, n, m - 1), m)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
mod = 1000000007
for line in sys.stdin:
	n = int(line.strip())
	print(pow(3, pow(3, n, mod - 1), mod))


import sys

def expo(a, p):
	x = 1
	t = 3 ** 500
	while a >= 500:
		x = x * t % p
		a -= 500
	return x * 3 ** a % p

def towerColoring(n):
	p = 1000000007
	e = expo(n, p - 1)
	return expo(e, p)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def totient(n):
	result = 1
	p = 2
	while p ** 2 <= n:
		if n % p == 0:
			result *= p - 1
			n /= p
		while n % p == 0:
			result *= p
			n /= p
		p += 1
	if n != 1:
		result *= n - 1
	return result

def modpow(p, z, b, c, m):
	cp = 0
	while m % p == 0:
		cp += 1
		m /= p
	t = totient(m)
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, m)

def towerColoring(a, b, c, m):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= modpow(p, z, b, c, m)
			result %= m
		p += 1
	if a != 1:
		result *= modpow(a, 1, b, c, m)
	return result % m
n = int(input().strip())
result = towerColoring(3, 3, n, 1000000007)
print(result)


import sys
mod = 1000000007

def towerColoring(n):
	return pow(3, pow(3, n, mod - 1), mod)
n = int(input().strip())
result = towerColoring(n)
print(result)


def totient(n):
	result = 1
	p = 2
	while p ** 2 <= n:
		if n % p == 0:
			result *= p - 1
			n /= p
		while n % p == 0:
			result *= p
			n /= p
		p += 1
	if n != 1:
		result *= n - 1
	return result

def modpow(p, z, b, c, m):
	cp = 0
	while m % p == 0:
		cp += 1
		m /= p
	t = totient(m)
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, m)

def solve(a, b, c, m):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= modpow(p, z, b, c, m)
			result %= m
		p += 1
	if a != 1:
		result *= modpow(a, 1, b, c, m)
	return result % m
n = int(input())
print(solve(3, 3, n, 1000000007))


import sys

def modular_power(b, e, m):
	ret = 1
	while e > 0:
		if e % 2 == 1:
			ret = ret * b % m
		e = e >> 1
		b = b * b % m
	return ret

def towerColoring(n):
	r = modular_power(3, n, 10 ** 9 + 6)
	return modular_power(3, r, 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def powermod3(a, b, n):
	r = 1
	while b > 0:
		if b % 2 == 1:
			r = r * a % n
		b //= 2
		a = a * a % n
	return r

def towerColoring(n):
	temp1 = powermod3(3, n, 1000000006)
	temp2 = powermod3(3, temp1, 1000000007)
	return temp2
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	max_ = 1000000007
	nn = pow(3, n, max_ - 1)
	return pow(3, nn, max_)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
import time
from math import log

def findPower(base, exp, mod=0):
	binaryPowerRep = bin(exp)[2:]
	binaryDigitParts = []
	for i in range(len(binaryPowerRep)):
		binaryDigitParts += [2 ** (len(binaryPowerRep) - 1 - i) * int(binaryPowerRep[i])]
	totals = []
	for power in binaryDigitParts:
		if power != 0:
			value = base
			for j in range(int(log(power, 2))):
				value **= 2
				if mod != 0:
					value %= mod
			totals.append(value)
	total = 1
	for i in totals:
		total *= i
		if mod != 0:
			total %= mod
	if mod == 0:
		return total
	else:
		return total % mod

def towerColoring3(n):
	stepOne = int(findPower(3, n, 10 ** 9 + 6))
	stepTwo = findPower(3, stepOne, 10 ** 9 + 7)
	return stepTwo
n = int(input().strip())
result = towerColoring3(n)
print(result)


import sys

def modPow(a, n, mod):
	x = 1
	while n > 0:
		if n % 2 == 1:
			x = x * a % mod
		n //= 2
		a = a ** 2 % mod
	return x

def towerColoring(n):
	MOD = int(10 ** 9 + 7)
	return modPow(3, modPow(3, n, MOD - 1), MOD)
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
mod = 1000000007
print(pow(3, pow(3, n, mod - 1), mod))


import sys
MODULO = 1000000007
POWER3_MODUL0 = {}

def fast_power_modulo(base, k):
	if k == 1:
		return base
	if k in POWER3_MODUL0:
		return POWER3_MODUL0[k]
	if k % 2 == 0:
		k1 = k // 2
		res = fast_power_modulo(base, k1)
		res = res * res % MODULO
	else:
		res = fast_power_modulo(base, k - 1)
		res = res * base % MODULO
	POWER3_MODUL0[k] = res
	return res
MODULO_MINUS1 = 1000000006
POWER3_MODUL0_MINUS1 = {}

def fast_power_module_minus1(base, k):
	if k == 1:
		return base
	if k in POWER3_MODUL0_MINUS1:
		return POWER3_MODUL0_MINUS1[k]
	if k % 2 == 0:
		k1 = k // 2
		res = fast_power_module_minus1(base, k1)
		res = res * res % MODULO_MINUS1
	else:
		res = fast_power_module_minus1(base, k - 1)
		res = res * base % MODULO_MINUS1
	POWER3_MODUL0_MINUS1[k] = res
	return res

def power_3_to_3_module(n):
	if n == 1:
		return 27
	nn = fast_power_module_minus1(3, n)
	res = fast_power_modulo(3, nn)
	return res

def towerColoring(n):
	return power_3_to_3_module(n)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
MOD = 10 ** 9 + 7

def towerColoring(n):
	power = pow(3, n, MOD - 1)
	ans = pow(3, power, MOD)
	return ans
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
M = 1000000007
T = M - 1

def towerColoring(n):
	x = pow(3, n, T)
	return pow(3, x, M)
n = int(input().strip())
result = towerColoring(n)
print(result)


def rp3(k, m):
	if k == 0:
		return 1
	e = rp3(k // 2, m)
	e = e * e % m
	if k % 2 == 1:
		e = e * 3 % m
	return e
n = int(input().strip())
p = 10 ** 9 + 7
r = rp3(n, p - 1)
print(rp3(r, p))


import sys

def totient(n):
	result = 1
	p = 2
	while p ** 2 <= n:
		if n % p == 0:
			result *= p - 1
			n /= p
		while n % p == 0:
			result *= p
			n /= p
		p += 1
	if n != 1:
		result *= n - 1
	return result

def modpow(p, z, b, c, m):
	cp = 0
	while m % p == 0:
		cp += 1
		m /= p
	t = totient(m)
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, m)

def solve(a, b, c, m):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= modpow(p, z, b, c, m)
			result %= m
		p += 1
	if a != 1:
		result *= modpow(a, 1, b, c, m)
	return result % m
n = int(input().strip())
result = solve(3, 3, n, 1000000007)
print(result)


import sys
modulo = 10 ** 9 + 7

def f(n):
	p0 = pow(3, n, modulo - 1)
	res = pow(3, p0, modulo)
	return res
n = int(input().strip())
result = f(n)
print(result)


import sys

def tower2(k, modulus):
	x = 3
	e = k
	y = 1
	m = modulus
	while e > 0:
		if e % 2 == 0:
			x = x * x % m
			e /= 2
		else:
			y = x * y % m
			e -= 1
	return y

def towerColoring(n):
	modulus = 10 ** 9 + 7
	phi_modulus = 10 ** 9 + 6
	b = tower2(n, phi_modulus)
	return tower2(b, modulus)
n = int(input().strip())
result = towerColoring(n)
print(result)


def totient(n):
	result = 1
	p = 2
	while p ** 2 <= n:
		if n % p == 0:
			result *= p - 1
			n /= p
		while n % p == 0:
			result *= p
			n /= p
		p += 1
	if n != 1:
		result *= n - 1
	return result

def modpow(p, z, b, c, m):
	cp = 0
	while m % p == 0:
		cp += 1
		m /= p
	t = totient(m)
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, m)

def solve(a, b, c, m):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= modpow(p, z, b, c, m)
			result %= m
		p += 1
	if a != 1:
		result *= modpow(a, 1, b, c, m)
	return result % m
n = int(input())
result = solve(3, 3, n, 1000000007)
print(result)


import sys

def towerColoring(n):
	x = pow(3, n, 1000000006)
	return pow(3, x, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def powerMod(a, b, n):
	if b == 0:
		return 1
	r = powerMod(a, b // 2, n)
	r = r * r % n
	if b % 2 == 1:
		r = r * a % n
	return r

def towerColoring(n):
	p = 10 ** 9 + 7
	m = 500000003
	return powerMod(3, powerMod(3, n, m), p)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	pr = 10 ** 9 + 7
	k = pow(3, n, pr - 1)
	ncol = pow(3, k, pr)
	return ncol
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
P = 10 ** 9 + 7
millions = n // 10 ** 6
n -= 10 ** 6 * millions
thousands = n // 10 ** 3
n -= 10 ** 3 * thousands
units = n
power = 1
for _ in range(millions):
	power = power * 286592977 % (P - 1)
for _ in range(thousands):
	power = power * 172803091 % (P - 1)
for _ in range(units):
	power = power * 3 % (P - 1)
del millions, thousands, units, _
millions = power // 10 ** 6
power -= 10 ** 6 * millions
thousands = power // 10 ** 3
power -= 10 ** 3 * thousands
units = power
del power
towers = 1
for _ in range(millions):
	towers = towers * 64935414 % (10 ** 9 + 7)
for _ in range(thousands):
	towers = towers * 56888193 % (10 ** 9 + 7)
for _ in range(units):
	towers = towers * 3 % (10 ** 9 + 7)
print(towers)


import sys
mod = 1000000007

def totient(n):
	result = 1
	p = 2
	while p ** 2 <= n:
		if n % p == 0:
			result *= p - 1
			n /= p
		while n % p == 0:
			result *= p
			n /= p
		p += 1
	if n != 1:
		result *= n - 1
	return result

def modpow(p, z, b, c, m):
	cp = 0
	while m % p == 0:
		cp += 1
		m /= p
	t = totient(m)
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, m)

def solve(a, b, c, m):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= modpow(p, z, b, c, m)
			result %= m
		p += 1
	if a != 1:
		result *= modpow(a, 1, b, c, m)
	return result % m

def towerColoring(n):
	return solve(3, 3, n, mod)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(a, n, m):
	number = 1
	while n:
		if n & 1:
			number = number * a % m
		n >>= 1
		a = a * a % m
	return number
n = int(input().strip())
m = 10 ** 9 + 7
result = towerColoring(3, n, m - 1)
result = towerColoring(3, result, m)
print(result)


import sys

def towerColoring(n):
	p = 10 ** 9 + 7
	return pow(3, pow(3, n, p - 1), p)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
import math

def power(p, z, b, c, m):
	cp = 0
	while m % p == 0:
		cp += 1
		m /= p
	t = m - 1
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, m)

def solve(a, b, c, m):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= power(p, z, b, c, m)
			result %= m
		p += 1
	if a != 1:
		result *= power(a, 1, b, c, m)
	return result % m

def towerColoring(n):
	return solve(3, 3, n, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
M = 1000000007
QR = 500000003
n = int(input().strip())
p = 1
n3r = 3
n3rs = [(1, 3)]
while p < n and n3r < QR:
	p += 1
	n3r *= 3
	if n3r >= QR:
		n3r = n3r % QR
		break
	n3rs.append((p, n3r))
while p < n:
	n3rs.append((p, n3r))
	p *= 2
	n3r = n3r * n3r % QR
n3r = 1
while n != 0:
	(p_i, n3r_i) = n3rs.pop()
	if p_i <= n:
		n -= p_i
		n3r = n3r * n3r_i % QR
p = 1
r = 3
rs = [(1, 3)]
while p < n3r and r < M:
	p += 1
	r *= 3
	if r >= M:
		r = r % M
		break
	rs.append((p, r))
while p < n3r:
	rs.append((p, r))
	p *= 2
	r = r * r % M
result = 1
while n3r != 0:
	(p_i, r_i) = rs.pop()
	if p_i <= n3r:
		n3r -= p_i
		result = result * r_i % M
print(result)


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 1000000006), 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
import math

def pow(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number

def towerColoring(n):
	return pow(3, pow(3, n, 10 ** 9 + 6), 10 ** 9 + 7)
n = int(input().strip())
result = towerColoring(n)
print(result)


def modpow(a, b, c):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % c
		a = a * a % c
		b >>= 1
	return res
n = int(input())
x = modpow(3, n, 1000000006)
y = modpow(3, x, 1000000007)
print(y)


import sys

def f(x, e, m):
	X = x
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
n = int(input().strip())
r = f(3, f(3, n % 1000000006, 1000000006), 1000000007)
print(r)


mod = 10 ** 9 + 7
for _ in range(1):
	b = str(input())
	b = int(b)
	b = b % (mod - 1)
	print(pow(3, pow(3, b, mod - 1), mod))


import sys

def towerColoring(n):
	n1 = pow(3, n, 1000000006)
	return pow(3, n1, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	n = n % 500000002
	a = pow(3, n, 1000000006)
	b = pow(3, a, 1000000007)
	return b
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
mod = 10 ** 9 + 7

def towerColoring(n):
	a = test(3, n, mod - 1)
	f = test(3, a, mod)
	return f

def test(x, n, modulo):
	x = x % modulo
	if n == 1:
		return x
	elif n % 2 == 0:
		return test(x * x % modulo, n // 2, modulo) % modulo
	else:
		return x * test(x * x % modulo, (n - 1) // 2, modulo) % modulo % modulo
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def getPower(a, b, limit):
	bits = []
	while b:
		bits.append(b % 2)
		b = int(b / 2)
	solution = 1
	bits.reverse()
	for x in bits:
		solution = solution % limit * (solution % limit) % limit
		if x:
			solution = solution % limit * (a % limit) % limit
	return solution

def towerColoring(n):
	limit = 1000000007
	return getPower(3, getPower(3, n, limit - 1), limit)
n = int(input().strip())
result = towerColoring(n)
print(result)


import math
modM = 10 ** 9 + 7
modN = 10 ** 9 + 6

def exp3(n):
	if n == 0:
		return 1
	x = exp3(n // 2)
	if n % 2 == 0:
		return x % modN * (x % modN) % modN
	else:
		return 3 * (x % modN) * (x % modN) % modN

def exp3modM(b, e, m=modM):
	x = 1
	while e > 0:
		if e % 2 == 1:
			(x, e) = (x * b % m, e - 1)
		else:
			(b, e) = (b * b % m, e // 2)
	return x

def towerColoring(n):
	stacks = exp3(n)
	return exp3modM(3, stacks)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
mod = 1000000007
mod1 = 1000000006 // 2

def power(n, p, m):
	p = int(p)
	n = int(n)
	if p == 0:
		return 1
	v = power(n, p // 2, m)
	if p % 2 == 0:
		return v * v % m
	else:
		return v * n % m * v % m

def towerColoring(n):
	cant = power(3, n, mod1)
	x = power(3, cant, mod)
	return x
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
import math

def power(p, z, b, c, m):
	cp = 0
	while m % p == 0:
		cp += 1
		m /= p
	t = m - 1
	exponent = (pow(b, c, t) * z % t + t - cp % t) % t
	return pow(p, cp) * pow(p, exponent, m)

def solve(a, b, c, m):
	result = 1
	p = 2
	while p ** 2 <= a:
		z = 0
		while a % p == 0:
			a /= p
			z += 1
		if z != 0:
			result *= power(p, z, b, c, m)
			result %= m
		p += 1
	if a != 1:
		result *= power(a, 1, b, c, m)
	return result % m

def towerColoring(n):
	return solve(3, 3, n, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys
import math

def towerColoring_correct(n):
	return pow(3, pow(3, n), 1000000007)

def simple_euler_totient(n):
	res = n
	for i in range(2, int(math.ceil(math.sqrt(n))) + 1):
		if n % i == 0:
			res -= res // i
			while n % i == 0:
				n //= i
	if n > 1:
		res -= res // n
	return res

def towerColoring(n):
	MOD = 1000000007
	t = simple_euler_totient(MOD)
	e = pow(3, n, t)
	return pow(3, e, MOD)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def power(n, mod):
	if n == 0:
		return 1
	if n == 1:
		return 3
	if n % 2 == 0:
		temp = power(int(n / 2), mod) % mod
		a = temp % mod * temp % mod % mod
		return a
	else:
		temp = power(int((n - 1) / 2), mod) % mod
		b = temp * temp % mod * 3 % mod
		return b

def towerColoring(n):
	a = power(n, 1000000006)
	return power(a, 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 500000003), 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def towerColoring(n):
	return pow(3, pow(3, n, 500000003), 1000000007)
n = int(input().strip())
result = towerColoring(n)
print(result)


import sys

def modr(x, power, p):
	res = 1
	while power > 0:
		if power % 2 == 1:
			res = res * x % p
		power = power // 2
		x = x * x % p
	return res

def towerColoring(n):
	p = 1000000007
	power = modr(3, n, p - 1)
	return modr(3, power, p)
n = int(input().strip())
result = towerColoring(n)
print(result)


import math
modnum = 10 ** 9 + 7

def modular_exp(a, b, n):
	d = 1
	B = [int(i) for i in list(bin(b)[2:])]
	for i in range(len(B)):
		d = d ** 2 % n
		if B[i] == 1:
			d = d * a % n
	return d

def towerColoring(n):
	exp = modular_exp(3, n, modnum - 1)
	ncolors = modular_exp(3, exp, modnum)
	return ncolors
n = int(input().strip())
result = towerColoring(n)
print(result)


n = int(input())
s = pow(10, 9) + 7
print(pow(3, pow(3, n, 500000003), 1000000007))


import sys
mod1 = 1000000006
mod2 = 1000000007

def tow(n, mud):
	i = 3
	s = 1
	while n > 0:
		if n % 2 == 1:
			s = s * i
			s = s % mud
		n = n // 2
		i = i * i % mud
	return s
n = int(input().strip())
m = tow(n, mod1)
result = tow(m, mod2)
print(result)


import sys
import math

def kp(o, b, c, m):
	tr = 1
	j = 2
	while j ** 2 <= o:
		z = 0
		while o % j == 0:
			o /= j
			z += 1
		if z != 0:
			tr *= yt(j, z, b, c, m)
			tr %= m
		j += 1
	if o != 1:
		tr *= yt(o, 1, b, c, m)
	return tr % m

def yt(lp, z, b, c, m):
	ku = 0
	while m % lp == 0:
		ku += 1
		m /= lp
	t = m - 1
	rg = (pow(b, c, t) * z % t + t - ku % t) % t
	return pow(lp, ku) * pow(lp, rg, m)

def mp(n):
	return kp(3, 3, n, 1000000007)
n = int(input())
gk = mp(n)
print(gk)


import sys
modulo = 10 ** 9 + 7
sys.setrecursionlimit(1000000)

def towerColoring(n):
	ans = pow(3, pow(3, n, modulo - 1), modulo)
	return ans
n = int(input().strip())
result = towerColoring(n)
print(result)