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: interview

Starter code:

Solutions:
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
# p to potega c
ef3 = (final[0][0] * 1) % N
ef2 = (final[0][1] * 1) % N
ef1 = (final[0][2] * 1) % N
# print f1^ef1 *f2^ef2*f3^ef3 * c^p
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)

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)


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 = list(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)


MOD = int(1e9 + 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]

#print(x, y, z)
#print(ini[3])
#print(w)
ans = (pow(c, w, MOD) * pow(f1, x, MOD) * pow(f2, y, MOD) * pow(f3, z, MOD)) % MOD 
print(ans)

# @author 

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_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)

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
#print(f1, f2, f3)
mat = [[1,1,1],[1,0,0],[0,1,0]]
res = power(mat, n-3)
#print(res)
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 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)

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)

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

#if there exists K such that X**K %mod == Y % mod, return K % (mod-1)
#Otherwise, return -1
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 = list(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))


import os
from io import BytesIO, StringIO
#input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

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()

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(temp1, temp2, temp3 , temp4)

print(ans)






        


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
#print(f1, f2, f3)
mat = [[1,1,1],[1,0,0],[0,1,0]]
res = power(mat, n-3)
#print(res)
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)

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])
	# print('a, b, c:', a, b, c)
	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 )

	# 		print('ans[', i, '][', j, '] = ', ans[i][j])
	# print('mult', M, 'and', K)
	# print(ans)
	return ans


def matrix_power(M, n):
	res = E
	mtpl = M
	# print('matrix_power, n =', n)
	while n:
		if n%2 == 1:
			res = mult(res, mtpl)
		mtpl = mult(mtpl, mtpl)
		n //= 2
	return res

n, f1, f2, f3, c = list(map(int, input().split()))
u = [c*f1 % mod,  c*c*f2 % mod, c*c*c*f3 % mod]
# print('u:', u)

Mn = matrix_power(M, n-4)
# print('Mn:', Mn)

pwrs = mult( [[1, 1, 1]], Mn )
# print('pwrs:', pwrs)

arr = [ pow(u[i], pwrs[0][i], mod) for i in range(3)]

un = reduce(lambda x, y: x*y%mod,  arr )
# print('un:', un)

cn_1 = pow(c, n*(mod-2) % (mod-1) , mod)
# print('cn', cn)

# cn_1 = pow(cn, mod-2, mod)
# print('cn_1', cn_1)
print((un * cn_1) % 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(fp1,fp2,fp3,cp)
print(r%MD)

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):
    """A**nをダブリングによって求める"""
    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)

def baby_step_giant_step(g, y, p):
    """y = g^x (mod p)を満たすxを求める"""
    m = int(p**0.5) + 1
    
    # Baby-step
    baby = {}
    b = 1
    for i in range(m):
        baby[b] = i
        b = (b * g) % p

    # Giant-step
    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):
    """A**nをダブリングによって求める"""
    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))

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 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)


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):
    nonlocal 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):
    nonlocal 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 = list(map(int, input().split()))

# [n-2, n-1, n]
x1_init = [1, 0, 0]
x1_mat = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 1, 1]
]

# [n-2, n-1, n]
x2_init = [0, 1, 0]
x2_mat = x1_mat

# [n-2, n-1, n]
x3_init = [0, 0, 1]
x3_mat = x1_mat

# [count_n-2, count_n-1, count_n, n, 1]
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)