Let $f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}$ for $x \ge 4$.

You have given integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$. Find $f_{n} \bmod (10^{9}+7)$.


-----Input-----

The only line contains five integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$ ($4 \le n \le 10^{18}$, $1 \le f_{1}$, $f_{2}$, $f_{3}$, $c \le 10^{9}$).


-----Output-----

Print $f_{n} \bmod (10^{9} + 7)$.


-----Examples-----
Input
5 1 2 5 3

Output
72900

Input
17 97 41 37 11

Output
317451037



-----Note-----

In the first example, $f_{4} = 90$, $f_{5} = 72900$.

In the second example, $f_{17} \approx 2.28 \times 10^{29587}$.

Difficulty: HARD
Tags: Matrices

Dynamic programming

Number theory

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
fib_matrix = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]

def matrix_square(A, mod):
	return mat_mult(A, A, mod)

def mat_mult(A, B, mod):
	if mod is not None:
		return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0] + A[0][2] * B[2][0]) % mod, (A[0][0] * B[0][1] + A[0][1] * B[1][1] + A[0][2] * B[2][1]) % mod, (A[0][0] * B[0][2] + A[0][1] * B[1][2] + A[0][2] * B[2][2]) % mod], [(A[1][0] * B[0][0] + A[1][1] * B[1][0] + A[1][2] * B[2][0]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1] + A[1][2] * B[2][1]) % mod, (A[1][0] * B[0][2] + A[1][1] * B[1][2] + A[1][2] * B[2][2]) % mod], [(A[2][0] * B[0][0] + A[2][1] * B[1][0] + A[2][2] * B[2][0]) % mod, (A[2][0] * B[0][1] + A[2][1] * B[1][1] + A[2][2] * B[2][1]) % mod, (A[2][0] * B[0][2] + A[2][1] * B[1][2] + A[2][2] * B[2][2]) % mod]]

def matrix_pow(M, power, mod):
	if power <= 0:
		return M
	powers = list(reversed([True if i == '1' else False for i in bin(power)[2:]]))
	matrices = [None for _ in powers]
	matrices[0] = M
	for i in range(1, len(powers)):
		matrices[i] = matrix_square(matrices[i - 1], mod)
	result = None
	for (matrix, power) in zip(matrices, powers):
		if power:
			if result is None:
				result = matrix
			else:
				result = mat_mult(result, matrix, mod)
	return result
fib_matrix2 = [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]

def matrix_square2(A, mod):
	return mat_mult2(A, A, mod)

def mat_mult2(A, B, mod):
	if mod is not None:
		m = []
		for i in range(5):
			m.append([])
			for j in range(5):
				sums = 0
				for k in range(5):
					sums += A[i][k] * B[k][j]
				m[-1].append(sums % mod)
		return m

def matrix_pow2(M, power, mod):
	if power <= 0:
		return M
	powers = list(reversed([True if i == '1' else False for i in bin(power)[2:]]))
	matrices = [None for _ in powers]
	matrices[0] = M
	for i in range(1, len(powers)):
		matrices[i] = matrix_square2(matrices[i - 1], mod)
	result = None
	for (matrix, power) in zip(matrices, powers):
		if power:
			if result is None:
				result = matrix
			else:
				result = mat_mult2(result, matrix, mod)
	return result
(n, f1, f2, f3, c) = map(int, input().split())
f3pow = matrix_pow(fib_matrix, n - 2, 1000000006)[0][2]
f1pow = matrix_pow(fib_matrix, n - 2, 1000000006)[1][2]
f2pow = matrix_pow(fib_matrix, n - 2, 1000000006)[1][1]
cpow = 2 * matrix_pow2(fib_matrix2, n, 1000000006)[2][4]
ans = pow(c, cpow, 1000000007)
ans = ans * pow(f1, f1pow, 1000000007) % 1000000007
ans = ans * pow(f2, f2pow, 1000000007) % 1000000007
ans = ans * pow(f3, f3pow, 1000000007) % 1000000007
print(ans)


from functools import reduce
mod = 10 ** 9 + 7
M = [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
E = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

def mult(M, K):
	(a, b, c) = (len(M), len(M[0]), len(K[0]))
	ans = [[0 for _ in range(c)] for _ in range(a)]
	for i in range(a):
		for j in range(c):
			for k in range(b):
				ans[i][j] += M[i][k] * K[k][j] % (mod - 1)
				ans[i][j] %= mod - 1
	return ans

def matrix_power(M, n):
	res = E
	mtpl = M
	while n:
		if n % 2 == 1:
			res = mult(res, mtpl)
		mtpl = mult(mtpl, mtpl)
		n //= 2
	return res
(n, f1, f2, f3, c) = map(int, input().split())
u = [c * f1 % mod, c * c * f2 % mod, c * c * c * f3 % mod]
Mn = matrix_power(M, n - 4)
pwrs = mult([[1, 1, 1]], Mn)
arr = [pow(u[i], pwrs[0][i], mod) for i in range(3)]
un = reduce(lambda x, y: x * y % mod, arr)
cn_1 = pow(c, n * (mod - 2) % (mod - 1), mod)
print(un * cn_1 % mod)


def mat_dot(A, B, mod):
	assert len(A[0]) == len(B), 'invalid_size'
	L = len(A)
	M = len(A[0])
	N = len(B[0])
	res = [[0] * N for _ in range(L)]
	for i in range(L):
		for j in range(N):
			a = 0
			for k in range(M):
				a = (a + A[i][k] * B[k][j]) % mod
			res[i][j] = a
	return res

def mat_pow(A, x, mod):
	N = len(A)
	res = [[0] * N for _ in range(N)]
	for i in range(N):
		res[i][i] = 1
	for i in range(x.bit_length()):
		if 2 ** i & x:
			res = mat_dot(res, A, mod)
		A = mat_dot(A, A, mod)
	return res

def bsgs(X, Y, mod):
	Y %= mod
	X %= mod
	rm = int(mod ** 0.5) + 2
	R = pow(pow(X, rm, mod), mod - 2, mod)
	D = {Y: 0}
	p = Y
	for a in range(1, rm):
		p = p * R % mod
		D[p] = a
	p = 1
	b = 0
	if p in D:
		return (D[p] * rm + b) % (mod - 1)
	for b in range(1, rm):
		p = p * X % mod
		if p in D:
			return (D[p] * rm + b) % (mod - 1)
	return -1
(n, f1, f2, f3, c) = map(int, input().split())
mod = 10 ** 9 + 7
a1 = bsgs(5, f1, mod)
a2 = bsgs(5, f2, mod)
a3 = bsgs(5, f3, mod)
d = bsgs(5, c, mod)
A = [[1, 1, 1, 2 * d, -6 * d], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]
B = mat_pow(A, n - 3, mod - 1)
Ans = mat_dot(B, [[a3], [a2], [a1], [4], [1]], mod - 1)
print(pow(5, Ans[0][0], mod))


def mul(a, b, mod):
	c = [[0] * len(b[0]) for i in range(len(a))]
	for i in range(len(a)):
		for j in range(len(b[0])):
			for k in range(len(b)):
				c[i][j] += a[i][k] * b[k][j]
				if c[i][j] > mod:
					c[i][j] %= mod
	return c

def power(val, p, mod):
	ans = [[1 if j == i else 0 for j in range(len(val))] for i in range(len(val))]
	while p:
		if p & 1:
			ans = mul(ans, val, mod)
		val = mul(val, val, mod)
		p >>= 1
	return ans
(n, f1, f2, f3, x) = list(map(int, input().split()))
n -= 1
mod = 1000000007
b1 = [[0], [0], [1]]
b2 = [[0], [1], [0]]
b3 = [[1], [0], [0]]
bc = [[0], [0], [0], [4], [1]]
m1 = m2 = m3 = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
mc = [[1, 1, 1, 2, -6], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]
a = pow(f1, mul(power(m1, n - 2, mod - 1), b1, mod - 1)[0][0], mod)
b = pow(f2, mul(power(m2, n - 2, mod - 1), b2, mod - 1)[0][0], mod)
c = pow(f3, mul(power(m3, n - 2, mod - 1), b3, mod - 1)[0][0], mod)
print(pow(x, mul(power(mc, n - 2, mod - 1), bc, mod - 1)[0][0], mod) * a * b * c % mod)


MD = 10 ** 9 + 7

def mult(A, B):
	n = len(A)
	C = [[0] * n for _ in range(n)]
	for i in range(len(A)):
		for j in range(len(A)):
			for k in range(len(A)):
				C[i][j] += A[i][k] * B[k][j]
			C[i][j] %= MD - 1
	return C

def ex(A, k):
	n = len(A)
	R = [[0] * n for _ in range(n)]
	for i in range(n):
		R[i][i] = 1
	while k > 0:
		if k & 1:
			R = mult(R, A)
		k //= 2
		A = mult(A, A)
	return R
cma = [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 2], [0, 0, 0, 0, 1]]
tri = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
(n, f1, f2, f3, c) = map(int, input().split())
ce = ex(cma, n - 3)
cp = ce[0][3] * 2 + ce[0][4]
f = ex(tri, n - 3)
fp1 = f[0][2]
fp2 = f[0][1]
fp3 = f[0][0]
r = pow(f1, fp1, MD) * pow(f2, fp2, MD) * pow(f3, fp3, MD) * pow(c, cp, MD)
print(r % MD)


(N, f1, f2, f3, x) = list(map(int, input().split()))

def mmult(A, B):
	nonlocal mod
	(n, m, l) = (len(A), len(B), len(B[0]))
	ret = [[0] * l for _ in range(n)]
	for i in range(n):
		for j in range(m):
			for k in range(l):
				ret[i][k] = (ret[i][k] + A[i][j] * B[j][k]) % mod
	return ret

def mpow(A, n):
	if n == 1:
		return A
	if n % 2:
		return mmult(mpow(A, n - 1), A)
	return mpow(mmult(A, A), n // 2)
P = 10 ** 9 + 7
mod = P - 1
X = [[1, 1, 0], [1, 0, 1], [1, 0, 0]]
Y = [[1, 1, 0, 0, 0], [1, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 1, 0], [1, 0, 0, 1, 1]]
a = 0 if N == 4 else mmult([[1, 0, 0]], mpow(X, N - 4))[0][0] % mod
b = mmult([[0, 1, 0]], mpow(X, N - 3))[0][0] % mod
c = mmult([[0, 0, 1]], mpow(X, N - 2))[0][0] % mod
d = mmult([[0, 0, 0, 0, 1]], mpow(Y, N - 3))[0][0] % mod
print(pow(f1, a, P) * pow(f2, b, P) * pow(f3, c, P) * pow(x * x, d, P) % P)


class Mat:

	def __init__(self, x):
		if x == 1:
			self.m = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
		else:
			self.m = [[x[i][j] for j in range(3)] for i in range(3)]

	def __mul__(self, other):
		return Mat([[sum((self.m[i][k] * other.m[k][j] for k in range(3))) % (mod - 1) for j in range(3)] for i in range(3)])

	def __rmul__(self, other):
		return Mat([[sum((other.m[i][k] * self.m[k][j] for k in range(3))) % (mod - 1) for j in range(3)] for i in range(3)])

	def __mod__(self, _mod):
		return Mat([[self.m[i][j] % _mod for j in range(3)] for i in range(3)])

def mat_bin_mod_pow(_mat, _mod, _pow):
	if _pow == 0:
		return Mat(1)
	return mat_bin_mod_pow(_mat * _mat % _mod, _mod, _pow >> 1) * (_mat if _pow & 1 else Mat(1)) % _mod

def bin_mod_pow(_num, _mod, _pow):
	if _pow == 0:
		return 1
	return bin_mod_pow(_num ** 2 % _mod, _mod, _pow >> 1) * (_num if _pow & 1 else 1) % _mod

def bin_mod_inv(_num, _mod):
	return bin_mod_pow(_num, _mod, _mod - 2) % _mod
mod = 10 ** 9 + 7
(n, f1, f2, f3, c) = map(int, input().split())
f = [f1, f2, f3]
g = [f[i] * c ** (i + 1) % mod for i in range(3)]
mat = Mat([[0, 1, 0], [0, 0, 1], [1, 1, 1]])
p = mat_bin_mod_pow(_mat=mat, _mod=mod - 1, _pow=n - 3).m[-1]
print(bin_mod_pow(_num=g[0], _mod=mod, _pow=p[0]) * bin_mod_pow(_num=g[1], _mod=mod, _pow=p[1]) * bin_mod_pow(_num=g[2], _mod=mod, _pow=p[2]) * bin_mod_pow(_num=bin_mod_inv(_num=c, _mod=mod), _mod=mod, _pow=n) % mod)


def mat_pow(mat, count):
	res = mat
	for x in map(int, bin(count)[3:]):
		res = mat_mat_mul(res, res)
		if x:
			res = mat_mat_mul(res, mat)
	return res

def mat_mat_mul(mat1, mat2):
	global mod
	d = len(mat1)
	res = []
	for row in range(d):
		res.append([])
		for col in range(d):
			cur = 0
			for i in range(d):
				cur += mat1[row][i] * mat2[i][col]
				cur %= mod - 1
			res[-1].append(cur)
	return res

def mat_vec_mul(mat, vec):
	global mod
	res = []
	for row in mat:
		cur = 0
		for (r, c) in zip(row, vec):
			cur += r * c
			cur %= mod - 1
		res.append(cur)
	return res
mod = 10 ** 9 + 7
(n, x1, x2, x3, c) = map(int, input().split())
x1_init = [1, 0, 0]
x1_mat = [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
x2_init = [0, 1, 0]
x2_mat = x1_mat
x3_init = [0, 0, 1]
x3_mat = x1_mat
c_init = [0, 0, 0, 3, 1]
c_mat = [[0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [1, 1, 1, 2, -4], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]
x1_count = mat_vec_mul(mat_pow(x1_mat, n - 1), x1_init)[0]
x2_count = mat_vec_mul(mat_pow(x2_mat, n - 1), x2_init)[0]
x3_count = mat_vec_mul(mat_pow(x3_mat, n - 1), x3_init)[0]
c_count = mat_vec_mul(mat_pow(c_mat, n - 1), c_init)[0]
ans = pow(c, c_count, mod) * pow(x1, x1_count, mod) * pow(x2, x2_count, mod) * pow(x3, x3_count, mod)
ans %= mod
print(ans)


def mat_mul(a, b):
	(n, m, p) = (len(a), len(b), len(b[0]))
	res = [[0] * p for _ in range(n)]
	for i in range(n):
		for j in range(p):
			for k in range(m):
				res[i][j] += a[i][k] * b[k][j]
			res[i][j] %= 1000000006
	return res

def mat_pow(a, n):
	if n == 1:
		return a
	if n % 2 == 1:
		return mat_mul(mat_pow(a, n - 1), a)
	t = mat_pow(a, n // 2)
	return mat_mul(t, t)
(n, f1, f2, f3, c) = map(int, input().split())
m1 = [[3, 1000000004, 0, 1000000005, 1], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]]
m2 = [[2], [0], [0], [0], [0]]
t1 = pow(c, mat_mul(mat_pow(m1, n), m2)[-1][0], 1000000007)
m1 = [[0, 0, 1], [1, 0, 1], [0, 1, 1]]
m2 = [[1], [0], [0]]
m3 = mat_mul(mat_pow(m1, n - 1), m2)
t2 = pow(f1, m3[0][0], 1000000007)
t3 = pow(f2, m3[1][0], 1000000007)
t4 = pow(f3, m3[2][0], 1000000007)
print(t1 * t2 * t3 * t4 % 1000000007)


MOD = int(1000000000.0 + 7)

def matMOD(A):
	f = lambda x: x % (MOD - 1)
	ret = [list(map(f, i)) for i in A]
	return ret

def matmul(A, B):
	(a, b) = (len(A), len(A[0]))
	c = len(B[0])
	ret = [[0] * c for i in range(a)]
	for i in range(a):
		for j in range(c):
			for k in range(b):
				ret[i][j] += A[i][k] * B[k][j]
	return ret

def matmul_log(A, m):
	if m == 1:
		return A
	B = matmul_log(A, m // 2)
	if m % 2 == 0:
		return matMOD(matmul(B, B))
	else:
		return matMOD(matmul(A, matmul(B, B)))
(n, f1, f2, f3, c) = map(int, input().split())
ini = [[1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [4, 2, 0, 0, 0, 2]]
m = [[0, 0, 0, 0], [1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1]]
m2 = [[1, 0, 0, 0, 0, 1], [1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 1, 1]]
M = matmul_log(m, n - 1)
M2 = matmul_log(m2, n - 1)
(x, y, z) = (matmul([ini[0]], M)[0][0], matmul([ini[1]], M)[0][0], matmul([ini[2]], M)[0][0])
w = matmul([ini[3]], M2)[0][2]
ans = pow(c, w, MOD) * pow(f1, x, MOD) * pow(f2, y, MOD) * pow(f3, z, MOD) % MOD
print(ans)


mod = 1000000007
X = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]

def mul(A, B):
	return [[sum((a * b for (a, b) in zip(X_row, Y_col))) % (mod - 1) for Y_col in zip(*B)] for X_row in A]

def pow_n(A, n):
	if n == 1:
		return A
	A_ = pow_n(A, n // 2)
	if n % 2 == 0:
		return A_ * A_ % mod
	else:
		return A_ * A_ * A % mod

def pow_m(A, n):
	if n == 1:
		return A
	A_ = pow_m(A, n // 2)
	if n % 2 == 0:
		return mul(A_, A_)
	else:
		return mul(mul(A_, A_), A)
(n, f1, f2, f3, c) = map(int, input().split())
u1 = c * f1 % mod
u2 = c ** 2 * f2 % mod
u3 = c ** 3 * f3 % mod
X_ = pow_m(X, n - 3)
u_n = pow_n(u3, X_[0][0]) * pow_n(u2, X_[0][1]) * pow_n(u1, X_[0][2]) % mod
f_n = pow_n(pow_n(c, mod - 2), n) * u_n % mod
print(f_n)


import sys

class EProductOrientedRecurrence:

	def solve(self):
		MOD = 10 ** 9 + 7
		D = 3
		I = [[1 if i == j else 0 for j in range(D)] for i in range(D)]

		def mat_mult(A, B):
			(n, m, p) = (len(A), len(A[0]), len(B[0]))
			assert len(B) == m
			C = [[0] * p for _ in range(n)]
			for i in range(n):
				for k in range(m):
					Aik = A[i][k]
					for j in range(p):
						C[i][j] = (C[i][j] + Aik * B[k][j]) % (MOD - 1)
			return C

		def mat_pow(A, p):
			if p == 0:
				return I
			if p == 1:
				return A
			if p % 2 == 0:
				return mat_pow(mat_mult(A, A), p // 2)
			else:
				return mat_mult(A, mat_pow(A, p - 1))
		(n, f1, f2, f3, c) = [int(_) for _ in input().split()]
		M = [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
		Rf1 = mat_mult(mat_pow(M, n - 1), [[1], [0], [0]])[0][0]
		Rf2 = mat_mult(mat_pow(M, n - 1), [[0], [1], [0]])[0][0]
		Rf3 = mat_mult(mat_pow(M, n - 1), [[0], [0], [1]])[0][0]
		Rpower = (mat_mult(mat_pow(M, n - 1), [[1], [2], [3]])[0][0] - n) % (MOD - 1)
		ans = pow(f1, Rf1, MOD) * pow(f2, Rf2, MOD) * pow(f3, Rf3, MOD) * pow(c, Rpower, MOD)
		ans %= MOD
		print(ans)
solver = EProductOrientedRecurrence()
input = sys.stdin.readline
solver.solve()


def mat_mult(A, B, MOD):
	(n, m, p) = (len(A), len(A[0]), len(B[0]))
	assert len(B) == m
	C = [[0] * p for _ in range(n)]
	for i in range(n):
		for k in range(m):
			Aik = A[i][k]
			for j in range(p):
				C[i][j] = (C[i][j] + Aik * B[k][j]) % MOD
	return C

def ksm(A, n, MOD):
	if n == 0:
		E = [[0 for i in range(len(A))] for j in range(len(A))]
		for i in range(len(A)):
			E[i][i] = 1
		return E
	if n == 1:
		return A
	k = ksm(A, n // 2, MOD)
	z = mat_mult(k, k, MOD)
	if n & 1:
		return mat_mult(z, A, MOD)
	else:
		return z

def Fenjie(n):
	k = {}
	if n == 1:
		return {}
	a = 2
	while n >= 2:
		b = n % a
		if a * a > n:
			k[n] = 1
			break
		if b == 0:
			if a in k:
				k[a] += 1
			else:
				k[a] = 1
			n = n // a
		else:
			a += 1
	return k

def Euler(n):
	if n == 1:
		return 1
	k = Fenjie(n)
	m = n
	for i in k:
		m = m // i * (i - 1)
	return m
MOD = 10 ** 9 + 7
(n, b, c, d, e) = list(map(int, input().split()))
l1 = [[0], [0], [1]]
l2 = [[0], [1], [0]]
l3 = [[1], [0], [0]]
l4 = [[6], [2], [0], [0], [0]]
a1 = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
a2 = [[3, -2, 0, -1, 1], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]]
if n == 4:
	print(e * e * b * c * d % MOD)
else:
	a1 = ksm(a1, n - 3, MOD - 1)
	a2 = ksm(a2, n - 5, MOD - 1)
	b1 = mat_mult(a1, l1, MOD - 1)
	p1 = pow(b, b1[0][0], MOD)
	c1 = mat_mult(a1, l2, MOD - 1)
	p2 = pow(c, c1[0][0], MOD)
	d1 = mat_mult(a1, l3, MOD - 1)
	p3 = pow(d, d1[0][0], MOD)
	n1 = mat_mult(a2, l4, MOD - 1)[0][0]
	p = pow(e, n1, MOD)
	p = p1 * p % MOD
	p = p2 * p % MOD
	p = p3 * p % MOD
	print(p)


def mult(m1, m2):
	p = len(m1)
	q = len(m2)
	r = len(m2[0])
	m3 = [[0] * r for _ in range(p)]
	for x in range(p):
		for y in range(r):
			for z in range(q):
				m3[x][y] += m1[x][z] * m2[z][y]
				m3[x][y] %= M - 1
	return m3

def binpow(mat, x):
	if x == 0:
		return E
	elif x % 2:
		return mult(mat, binpow(mult(mat, mat), x // 2))
	else:
		return binpow(mult(mat, mat), x // 2)
matrix = [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
E = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
M = 10 ** 9 + 7
(n, f1, f2, f3, c) = map(int, input().split())
matrix = binpow(matrix, n - 1)
g1 = matrix[0][0]
g2 = matrix[0][1]
g3 = matrix[0][2]
ans = pow(c * f1, g1, M) * pow(c * c * f2, g2, M) % M * pow(c * c * c * f3, g3, M) % M * pow(c, (10 ** 9 * (M - 1) - n) % (M - 1), M) % M
print(ans % M)


def mat_mul(A, B, m):
	C = [[0] * 3 for i in range(3)]
	for i in range(3):
		for j in range(3):
			C[i][j] = (A[i][0] * B[0][j] % m + A[i][1] * B[1][j] % m + A[i][2] * B[2][j] % m) % m
	return C

def vec_mul(A, x, m):
	b = [0] * 3
	for i in range(3):
		b[i] = (A[i][0] * x[0] % m + A[i][1] * x[1] % m + A[i][2] * x[2] % m) % m
	return b

def calc_tribonacci(M, n, m, start):
	X = []
	X.append(M[0].copy())
	X.append(M[1].copy())
	X.append(M[2].copy())
	R = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	while n > 0:
		if n % 2 == 1:
			R = mat_mul(X, R, m)
		X = mat_mul(X, X, m)
		n = n // 2
	return vec_mul(R, start, m)[2]

def calc_exponent(a, b, m):
	x = a
	r = 1
	while b > 0:
		if b % 2 == 1:
			r = r * x % m
		x = x * x % m
		b = b // 2
	return r
m = 1000000007
(n, f1, f2, f3, c) = [int(i) for i in input().split()]
M = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
temp1 = 3 * calc_tribonacci(M, n - 1, m - 1, [1, 1, 0])
temp1 = (temp1 - calc_tribonacci(M, n - 4, m - 1, [1, 1, 0]) - n) % (m - 1)
temp2 = calc_tribonacci(M, n - 3, m - 1, [2, 1, 1])
temp3 = calc_tribonacci(M, n - 3, m - 1, [2, 1, 0])
temp4 = calc_tribonacci(M, n - 3, m - 1, [1, 1, 0])
ans = calc_exponent(c, temp1, m)
ans = ans * calc_exponent(f3, temp2, m) % m
ans = ans * calc_exponent(f2, temp3, m) % m
ans = ans * calc_exponent(f1, temp4, m) % m
print(ans)


import os
from io import BytesIO, StringIO
DEBUG = False
debug_print = print if DEBUG else lambda *x, **y: None

def input_as_list():
	return list(map(int, input().split()))

def array_of(f, *dim):
	return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
	mod = 1000000007

	def modmul(x, y):
		return x * y % mod

	def row(m, i, n=3):
		return m[n * i:n * (i + 1)]

	def col(m, i, n=3):
		return m[i::n]

	def vecmul(u, v):
		s = 0
		for (i, j) in zip(u, v):
			s += i * j % (mod - 1)
		return s % (mod - 1)

	def matmul(a, b, n=3):
		out = []
		for i in range(n * n):
			(r, c) = divmod(i, n)
			out.append(vecmul(row(a, r), col(b, c)))
		return out

	def matadd(a, b, n=3):
		out = []
		for i in range(n * n):
			out.append((a[i] + b[i]) % (mod - 1))
		return out

	def matpow(m, p, n=3):
		bs = str(bin(p)).lstrip('0b')
		out = [0] * (n * n)
		out[0::n + 1] = [1] * n
		for b in reversed(bs):
			if b == '1':
				out = matmul(out, m)
			m = matmul(m, m)
		return out

	def brute_force(n, f1, f2, f3, c):
		i = 3
		while i < n:
			i += 1
			f4 = pow(c, 2 * i - 6, mod) * f1 * f2 * f3 % mod
			(f1, f2, f3) = (f2, f3, f4)
		return f3

	def solve(n, f1, f2, f3, c):
		f = [f1, f2, f3]
		g = [modmul(c, f[0]), modmul(c * c, f[1]), modmul(c * c * c, f[2])]
		mat = [1, 1, 1, 1, 0, 0, 0, 1, 0]
		mat_n = matpow(mat, n - 3)
		g_n = pow(g[2], mat_n[0], mod) * pow(g[1], mat_n[1], mod) * pow(g[0], mat_n[2], mod) % mod
		c_n = pow(c, n, mod)
		c_n_inv = pow(c_n, mod - 2, mod)
		f_n = modmul(g_n, c_n_inv)
		return f_n

	def solve_from_stdin():
		i = input_as_list()
		print(solve(*i))

	def test():
		import random
		sample = [random.randrange(4, 99) for _ in range(5)]
		sample = [2, 2, 2, 2]
		print(*sample)
		for i in range(4, 200):
			print(i, *sample)
			print(solve(i, *sample))
			print(brute_force(i, *sample))
			print()
	solve_from_stdin()
main()


MOD = 10 ** 9 + 7

def mat_mul(m1, m2):
	n = len(m1)
	m = []
	for _ in range(n):
		m.append([0] * n)
	for y in range(n):
		for x in range(n):
			for i in range(n):
				m[y][x] += m1[y][i] * m2[i][x]
	for y in range(n):
		for x in range(n):
			m[y][x] %= MOD - 1
	return m

def square_and_multiply(m, exp):
	if exp == 1:
		return m
	sub = square_and_multiply(m, exp // 2)
	sqr = mat_mul(sub, sub)
	if exp % 2 == 1:
		return mat_mul(sqr, m)
	return sqr
(n, f1, f2, f3, c) = map(int, input().split())
mf = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
mc = [[1, 0, 0, 0, 1], [2, 1, 1, 1, -4], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 1]]
matf = square_and_multiply(mf, n - 3)
matc = square_and_multiply(mc, n - 3)
c_exp = matc[1][0] * 3 + matc[1][4]
f3_exp = matf[0][0]
f2_exp = matf[0][1]
f1_exp = matf[0][2]
res = pow(c, c_exp, MOD) * pow(f3, f3_exp, MOD) * pow(f2, f2_exp, MOD) * pow(f1, f1_exp, MOD)
print(res % MOD)


def _mul(A, B, MOD):
	C = [[0] * len(B[0]) for i in range(len(A))]
	for i in range(len(A)):
		for k in range(len(B)):
			for j in range(len(B[0])):
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
	return C

def pow_matrix(A, n, MOD):
	B = [[0] * len(A) for i in range(len(A))]
	for i in range(len(A)):
		B[i][i] = 1
	while n > 0:
		if n & 1:
			B = _mul(A, B, MOD)
		A = _mul(A, A, MOD)
		n = n // 2
	return B
(n, f1, f2, f3, c) = map(int, input().split())
MOD = 10 ** 9 + 7
ans = 1
matrix = [[0] * 3 for i in range(3)]
matrix[0][0] = matrix[0][1] = matrix[0][2] = 1
matrix[1][0] = 1
matrix[2][1] = 1
f_matrix = pow_matrix(matrix, n - 3, MOD - 1)
ans *= pow(f3, f_matrix[0][0], MOD)
ans *= pow(f2, f_matrix[0][1], MOD)
ans *= pow(f1, f_matrix[0][2], MOD)
matrix = [[0] * 5 for i in range(5)]
matrix[0][0] = matrix[0][1] = matrix[0][2] = 1
matrix[0][3] = 2
matrix[0][4] = -6
matrix[1][0] = matrix[2][1] = 1
matrix[3][3] = matrix[3][4] = 1
matrix[4][4] = 1
c_matrix = pow_matrix(matrix, n - 3, MOD - 1)
ans *= pow(c, c_matrix[0][3] * 4 + c_matrix[0][4], MOD)
print(ans % MOD)


import math
md = 10 ** 9 + 7

def multiply(M, N):
	md2 = 10 ** 9 + 6
	R = [[0 for i in range(3)] for j in range(3)]
	for i in range(0, 3):
		for j in range(0, 3):
			for k in range(0, 3):
				R[i][j] += M[i][k] * N[k][j] % md2
				R[i][j] %= md2
	return R

def power(mat, n):
	res = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	while n:
		if n & 1:
			res = multiply(res, mat)
		mat = multiply(mat, mat)
		n //= 2
	return res
(n, f1, f2, f3, c) = map(int, input().split())
f1 = f1 * c % md
f2 = f2 * c ** 2 % md
f3 = f3 * c ** 3 % md
mat = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
res = power(mat, n - 3)
(pw1, pw2, pw3) = (res[0][2], res[0][1], res[0][0])
f1 = pow(f1, pw1, md)
f2 = pow(f2, pw2, md)
f3 = pow(f3, pw3, md)
ans = f1 * f2 % md * f3 % md
c = pow(c, md - 2, md)
ans *= pow(c, n % (md - 1), md)
ans %= md
print(ans)


def baby_step_giant_step(g, y, p):
	m = int(p ** 0.5) + 1
	baby = {}
	b = 1
	for i in range(m):
		baby[b] = i
		b = b * g % p
	gm = pow(b, p - 2, p)
	giant = y
	for i in range(m):
		if giant in baby:
			x = i * m + baby[giant]
			return x
		giant = giant * gm % p
	return -1

def _mul(A, B, MOD):
	C = [[0] * len(B[0]) for i in range(len(A))]
	for i in range(len(A)):
		for k in range(len(B)):
			for j in range(len(B[0])):
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
	return C

def pow_matrix(A, n, MOD):
	B = [[0] * len(A) for i in range(len(A))]
	for i in range(len(A)):
		B[i][i] = 1
	while n > 0:
		if n & 1:
			B = _mul(A, B, MOD)
		A = _mul(A, A, MOD)
		n = n // 2
	return B
(n, f1, f2, f3, c) = map(int, input().split())
MOD = 10 ** 9 + 7
log_f1 = baby_step_giant_step(5, f1, MOD)
log_f2 = baby_step_giant_step(5, f2, MOD)
log_f3 = baby_step_giant_step(5, f3, MOD)
log_c = baby_step_giant_step(5, c, MOD)
matrix = [[0] * 5 for i in range(5)]
matrix[0][0] = 1
matrix[0][1] = 1
matrix[0][2] = 1
matrix[0][3] = 2 * log_c
matrix[0][4] = -6 * log_c
matrix[1][0] = 1
matrix[2][1] = 1
matrix[3][3] = 1
matrix[3][4] = 1
matrix[4][4] = 1
matrix_n = pow_matrix(matrix, n - 3, MOD - 1)
ans = log_f3 * matrix_n[0][0] + log_f2 * matrix_n[0][1] + log_f1 * matrix_n[0][2] + 4 * matrix_n[0][3] + matrix_n[0][4]
ans = ans % (MOD - 1)
print(pow(5, ans, MOD))


(n, f1, f2, f3, c) = list(map(int, input().split()))
mat = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
final = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
nn = n - 3
N = 10 ** 9 + 6

def prod(a, b):
	m = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
	for i in range(3):
		for j in range(3):
			m[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j]) % N
	return m
while nn > 0:
	if nn % 2 == 1:
		final = prod(final, mat)
	mat = prod(mat, mat)
	nn //= 2
q = (final[0][0] * 3 + final[0][1] * 2 + final[0][2] * 1) % N
p = q - n % N + N
ef3 = final[0][0] * 1 % N
ef2 = final[0][1] * 1 % N
ef1 = final[0][2] * 1 % N

def pot(a, w):
	wyn = 1
	while w > 0:
		if w % 2 == 1:
			wyn = wyn * a % (N + 1)
		a = a * a % (N + 1)
		w //= 2
	return wyn
l1 = pot(f1, ef1)
l2 = pot(f2, ef2)
l3 = pot(f3, ef3)
l4 = pot(c, p)
c = l1 * l2 * l3 * l4 % (N + 1)
print(c)