After Derek (of district 5) discovered how to compute the greatest common divisor (gcd) of Fibonacci numbers, he now tried to answer the next obvious question: how does one compute the least common multiple (lcm) of Fibonacci numbers? Unfortunately, Derek found out that this wasn't as easy as the original problem, so he asked you to answer it for him.

The Fibonacci numbers are defined as:

$F_1=F_2=1$
$F_n=F_{n-1}+F_{n-2}$

Given $N$ integers $a_1,a_2,\ldots,a_N$, find $\text{lcm}(F_{a_1},F_{a_2},\ldots,F_{a_N})$, and give your answer modulo $10^9+7$.

Input Format 

The first line of input contains $N$. 

Each of the next $N$ lines contains a number: the $i^{th}$ line contains $a_i$.

Constraints 

$1\leq N\leq100$ 

$1\leq a_i\leq10^9$  

Output Format 

Print a single integer, which is the least common multiple of the ${F}_{a_i}$, modulo $10^9+7$.

Sample Input  

5
1
3
3
6
9

Sample Output  

136

Explanation 

$\text{lcm}(F_1,F_3,F_3,F_6,F_9)=\text{lcm}(1,2,2,8,34)=136$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
import sys, random
from math import sqrt

def gcd(a, b):
	while 1:
		if b == 0:
			return a
		a %= b
		if a == 0:
			return b
		b %= a

def fib_mod(n, mod):
	if n <= 2:
		return ((n + 1 >> 1) % mod, (n + 2 >> 1) % mod)
	mask = 4
	while mask <= n:
		mask <<= 1
	mask >>= 2
	(a, b) = (1, 1)
	while mask:
		if mask & n:
			(a, b) = ((a * a + b * b) % mod, b * ((a << 1) + b) % mod)
		else:
			(a, b) = (a * ((b << 1) - a) % mod, (a * a + b * b) % mod)
		mask >>= 1
	return (a, b)

def divisors(n):
	l = [1]
	f = factors(n)
	for (p, e) in f:
		for i in range(len(l)):
			v = l[i]
			for j in range(e):
				v *= p
				l.append(v)
	return sorted(l)

def p6():

	def solve(seq):
		seq = sorted(seq)
		next = []
		for i in range(len(seq)):
			for j in range(i + 1, len(seq)):
				if seq[j] % seq[i] == 0:
					break
			else:
				next.append(seq[i])
		seq = next[:]
		ans = 1
		for i in range(len(seq)):
			c = seq[i]
			ans = ans * fib_mod(c, MOD)[0] % MOD
			t = 1
			s = set()
			for g in seq[:i]:
				s.add(gcd(g, c))
			s = list(sorted(s))
			k = solve(s)
			ans = ans * pow(k, MOD - 2, MOD) % MOD
		return ans
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	seq = []
	for _ in range(T):
		N = int(stdin.readline())
		seq.append(N)
	print(solve(seq))
p6()


import fractions, sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P

def fibonacci(N):
	return matrix_exp(FIB_MATRIX, N)[1][0]

def modinv(n):
	return pow(n, MOD - 2, MOD)
memo = {}

def lcm(A, k, i):
	if (k, i) not in memo:
		if i == 0:
			memo[k, i] = 1
		else:
			gcd = fractions.gcd(k, A[i - 1])
			if gcd == k:
				memo[k, i] = fibonacci(gcd) % MOD
			else:
				memo[k, i] = fibonacci(gcd) * lcm(A, k, i - 1) * modinv(lcm(A, gcd, i - 1)) % MOD
	return memo[k, i]
N = int(sys.stdin.readline())
A = list(set((int(sys.stdin.readline()) for _ in range(N))))
print(lcm(A, 0, len(A)))


import fractions, sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P

def fibonacci(N):
	return matrix_exp(FIB_MATRIX, N)[1][0]

def modinv(n):
	return pow(n, MOD - 2, MOD)
memo = {}

def lcm(A, k, i):
	if (k, i) not in memo:
		if i == 0:
			memo[k, i] = 1
		else:
			gcd = fractions.gcd(k, A[i - 1])
			if gcd == k:
				memo[k, i] = fibonacci(gcd) % MOD
			else:
				memo[k, i] = fibonacci(gcd) * lcm(A, k, i - 1) * modinv(lcm(A, gcd, i - 1)) % MOD
	return memo[k, i]
N = int(sys.stdin.readline())
A = list(set((int(sys.stdin.readline()) for _ in range(N))))
print(lcm(A, 0, len(A)))


import fractions, sys
MOD = 1000000007
FIB_MATRIX = [[1, 1], [1, 0]]

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]

def matrix_exp(A, N):
	M = [[1, 0], [0, 1]]
	if N == 0:
		return M
	elif N == 1:
		return A
	else:
		P = matrix_exp(A, N // 2)
		P = matrix_mult(P, P)
		if N % 2 == 1:
			P = matrix_mult(P, A)
		return P

def fibonacci(N):
	return matrix_exp(FIB_MATRIX, N)[1][0]

def modinv(n):
	return pow(n, MOD - 2, MOD)
memo = {}

def lcm(A, k, i):
	if (k, i) not in memo:
		if i == 0:
			memo[k, i] = 1
		else:
			gcd = fractions.gcd(k, A[i - 1])
			if gcd == k:
				memo[k, i] = fibonacci(gcd) % MOD
			else:
				memo[k, i] = fibonacci(gcd) * lcm(A, k, i - 1) * modinv(lcm(A, gcd, i - 1)) % MOD
	return memo[k, i]
N = int(sys.stdin.readline())
A = list(set((int(sys.stdin.readline()) for _ in range(N))))
print(lcm(A, 0, len(A)))


import sys, math, itertools, datetime
from collections import Counter, deque, defaultdict
from functools import reduce
debug_tlast = [None]
debug_enabled = [False]

def debug(s):
	if debug_enabled[0]:
		t1 = datetime.datetime.utcnow()
		secs = (t1 - debug_tlast[0]).total_seconds() if debug_tlast[0] else 0
		debug_tlast[0] = t1
		print('[DEBUG] [{:.3f}] {}'.format(secs, s), file=sys.stderr)

def modular_inverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def modular_power(a, n, m):
	if n == 0:
		return 1
	a = a % m
	if a < 0:
		a += m
	prod = 1
	pwr = a
	while n != 0:
		if n % 2 != 0:
			prod = prod * pwr % m
		n >>= 1
		if n == 0:
			break
		pwr = pwr * pwr % m
	return prod

def build_powers(a, exps, id, square, mult):
	bitToIndices = defaultdict(list)
	maxbit = 0
	for (i, x) in enumerate(exps):
		j = 0
		while x != 0:
			if x & 1 != 0:
				bitToIndices[j].append(i)
				maxbit = max(maxbit, j)
			j += 1
			x = x // 2
	prods = [id() for _ in range(len(exps))]
	for j in range(maxbit + 1):
		for i in bitToIndices[j]:
			prods[i] = mult(prods[i], a)
		a = square(a)
	return prods

def power_peasant_3(a, n, mult3, unity):
	adim = len(a)
	prod = unity
	tmp = [[0] * adim for _ in range(adim)]
	pwr = a
	while n != 0:
		if n % 2 != 0:
			mult3(tmp, prod, pwr)
			(tmp, prod) = (prod, tmp)
		n >>= 1
		if n == 0:
			break
		mult3(tmp, pwr, pwr)
		(tmp, pwr) = (pwr, tmp)
	return prod

def fibo_mod(n, MOD):
	A = [[1, 1], [1, 0]]

	def mult3(R, B, C):
		R[0][0] = (B[0][0] * C[0][0] + B[0][1] * C[1][0]) % MOD
		R[0][1] = (B[0][0] * C[0][1] + B[0][1] * C[1][1]) % MOD
		R[1][0] = (B[1][0] * C[0][0] + B[1][1] * C[1][0]) % MOD
		R[1][1] = (B[1][0] * C[0][1] + B[1][1] * C[1][1]) % MOD
	I = [[1, 0], [0, 1]]
	An = power_peasant_3(A, n, mult3, I)
	Fn = An[1][0]
	return Fn

def fibo_mods(exps, MOD):
	F = [[1, 1], [1, 0]]

	def mult(B, C):
		return [[(B[0][0] * C[0][0] + B[0][1] * C[1][0]) % MOD, (B[0][0] * C[0][1] + B[0][1] * C[1][1]) % MOD], [(B[1][0] * C[0][0] + B[1][1] * C[1][0]) % MOD, (B[1][0] * C[0][1] + B[1][1] * C[1][1]) % MOD]]

	def id():
		return [[1, 0], [0, 1]]

	def square(A):
		return mult(A, A)
	Apwrs = build_powers(F, exps, id, square, mult)
	return [Ap[1][0] % MOD for Ap in Apwrs]

def fibolcm(a, MOD):
	a = sorted(set(a) - {1, 2})
	debug('{} fibos to LCM'.format(len(a)))
	if True:
		a2 = []
		for (i, x) in enumerate(a):
			include = True
			for y in a[i + 1:]:
				if y % x == 0:
					include = False
					break
			if include:
				a2.append(x)
		debug('Removed {} proper divisors'.format(len(a) - len(a2)))
		a = a2
	(fcache, icache, gcdcache) = ({}, {}, {})

	def F(n):
		y = fcache.get(n)
		if y is None:
			y = fcache[n] = fibo_mod(n, MOD)
		return y

	def Inv(n):
		y = icache.get(n)
		if y is None:
			y = icache[n] = modular_inverse(n, MOD)
		return y

	def GCD(a, b):
		if a > b:
			(a, b) = (b, a)
		y = gcdcache.get((a, b))
		if y is None:
			y = gcdcache[a, b] = math.gcd(a, b)
		return y
	debug('Walking tree')

	def flcm_count(k, g, a, ndivisible, counts):
		if k == 0:
			for (i, x) in enumerate(a):
				flcm_count(k + 1, x, a[i + 1:], ndivisible, counts)
		else:
			for (i, x) in enumerate(a):
				if x % g == 0:
					ndivisible += 1
				else:
					g2 = math.gcd(g, x)
					if g2 != 1:
						flcm_count(k + 1, g2, a[i + 1:], ndivisible, counts)
			if ndivisible == 0:
				if k % 2 == 1:
					counts[g] += 1
				else:
					counts[g] -= 1
	counts = Counter()
	flcm_count(0, 0, a, 0, counts)
	debug('Building fibos')
	exps = [g for (g, c) in counts.items() if c != 0]
	fibos = fibo_mods(exps, MOD)
	fibos = {exps[i]: x for (i, x) in enumerate(fibos)}
	y = 1
	for (g, c) in counts.items():
		if c == 0:
			continue
		p = fibos[g]
		if c < 0:
			p = Inv(p)
			c = -c
		p = modular_power(p, c, MOD)
		y = y * p % MOD
	debug('Done')
	return y

def main():
	if len(sys.argv) >= 2 and sys.argv[1] == '--debug':
		debug_enabled[0] = True
	MOD = 10 ** 9 + 7
	n = int(sys.stdin.readline())
	a = []
	for _ in range(n):
		ai = int(sys.stdin.readline())
		a.append(ai)
	print(fibolcm(a, MOD))
main()


from fractions import gcd
import sys
sys.setrecursionlimit(10 ** 9)
p = 10 ** 9 + 7

def matrix_mul(A, B, p=10 ** 9 + 7):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p]]

def matrix_pow(A, n, p=10 ** 9 + 7):
	if n == 0:
		return [[1, 0], [0, 1]]
	B = matrix_pow(A, n // 2, p)
	B = matrix_mul(B, B, p)
	if n % 2 == 1:
		B = matrix_mul(B, A, p)
	return B

def fibonacci(A, B, n, p=10 ** 9 + 7):
	M = matrix_pow([[1, 1], [1, 0]], n, p)
	return (M[1][0] * B + M[1][1] * A) % p

def fib_lcm(A):
	if len(A) == 1:
		return fibonacci(0, 1, A[0])
	B = list(set([gcd(A[0], a) for a in A[1:]]))
	return fib_lcm(A[1:]) * fibonacci(0, 1, A[0]) * pow(fib_lcm(B), p - 2, p) % p
N = int(input())
A = [int(input()) for _ in range(N)]
print(fib_lcm(A))


from fractions import gcd
import sys
sys.setrecursionlimit(10 ** 9)
p = 10 ** 9 + 7

def matrix_mul(A, B, p=10 ** 9 + 7):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p]]

def matrix_pow(A, n, p=10 ** 9 + 7):
	if n == 0:
		return [[1, 0], [0, 1]]
	B = matrix_pow(A, n // 2, p)
	B = matrix_mul(B, B, p)
	if n % 2 == 1:
		B = matrix_mul(B, A, p)
	return B

def fibonacci(A, B, n, p=10 ** 9 + 7):
	M = matrix_pow([[1, 1], [1, 0]], n, p)
	return (M[1][0] * B + M[1][1] * A) % p

def fib_lcm(A):
	if len(A) == 1:
		return fibonacci(0, 1, A[0])
	B = list(set([gcd(A[0], a) for a in A[1:]]))
	return fib_lcm(A[1:]) * fibonacci(0, 1, A[0]) * pow(fib_lcm(B), p - 2, p) % p
N = int(input())
A = [int(input()) for _ in range(N)]
print(fib_lcm(A))


from fractions import gcd
import sys
sys.setrecursionlimit(10 ** 9)
p = 10 ** 9 + 7

def matrix_mul(A, B, p=10 ** 9 + 7):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p]]

def matrix_pow(A, n, p=10 ** 9 + 7):
	if n == 0:
		return [[1, 0], [0, 1]]
	B = matrix_pow(A, n // 2, p)
	B = matrix_mul(B, B, p)
	if n % 2 == 1:
		B = matrix_mul(B, A, p)
	return B

def fibonacci(A, B, n, p=10 ** 9 + 7):
	M = matrix_pow([[1, 1], [1, 0]], n, p)
	return (M[1][0] * B + M[1][1] * A) % p

def fib_lcm(A):
	if len(A) == 1:
		return fibonacci(0, 1, A[0])
	B = list(set([gcd(A[0], a) for a in A[1:]]))
	return fib_lcm(A[1:]) * fibonacci(0, 1, A[0]) * pow(fib_lcm(B), p - 2, p) % p
N = int(input())
A = [int(input()) for _ in range(N)]
print(fib_lcm(A))


import sys, random
from math import sqrt

def gcd(a, b):
	while 1:
		if b == 0:
			return a
		a %= b
		if a == 0:
			return b
		b %= a

def fib_mod(n, mod):
	if n <= 2:
		return ((n + 1 >> 1) % mod, (n + 2 >> 1) % mod)
	mask = 4
	while mask <= n:
		mask <<= 1
	mask >>= 2
	(a, b) = (1, 1)
	while mask:
		if mask & n:
			(a, b) = ((a * a + b * b) % mod, b * ((a << 1) + b) % mod)
		else:
			(a, b) = (a * ((b << 1) - a) % mod, (a * a + b * b) % mod)
		mask >>= 1
	return (a, b)

def divisors(n):
	l = [1]
	f = factors(n)
	for (p, e) in f:
		for i in range(len(l)):
			v = l[i]
			for j in range(e):
				v *= p
				l.append(v)
	return sorted(l)

def p6():

	def solve(seq):
		seq = sorted(seq)
		next = []
		for i in range(len(seq)):
			for j in range(i + 1, len(seq)):
				if seq[j] % seq[i] == 0:
					break
			else:
				next.append(seq[i])
		seq = next[:]
		ans = 1
		for i in range(len(seq)):
			c = seq[i]
			ans = ans * fib_mod(c, MOD)[0] % MOD
			t = 1
			s = set()
			for g in seq[:i]:
				s.add(gcd(g, c))
			s = list(sorted(s))
			k = solve(s)
			ans = ans * pow(k, MOD - 2, MOD) % MOD
		return ans
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	seq = []
	for _ in range(T):
		N = int(stdin.readline())
		seq.append(N)
	print(solve(seq))
p6()


import math
from math import gcd
import sys
sys.setrecursionlimit(10 ** 9)
p = 10 ** 9 + 7

def matrix_mul(A, B, p=10 ** 9 + 7):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p]]

def matrix_pow(A, n, p=10 ** 9 + 7):
	if n == 0:
		return [[1, 0], [0, 1]]
	B = matrix_pow(A, n // 2, p)
	B = matrix_mul(B, B, p)
	if n % 2 == 1:
		B = matrix_mul(B, A, p)
	return B

def fibonacci(A, B, n, p=10 ** 9 + 7):
	M = matrix_pow([[1, 1], [1, 0]], n, p)
	return (M[1][0] * B + M[1][1] * A) % p

def fib_lcm(A):
	if len(A) == 1:
		return fibonacci(0, 1, A[0])
	B = list(set([gcd(A[0], a) for a in A[1:]]))
	return fib_lcm(A[1:]) * fibonacci(0, 1, A[0]) * pow(fib_lcm(B), p - 2, p) % p
N = int(input())
A = [int(input()) for _ in range(N)]
print(fib_lcm(A))


import sys, random
from math import sqrt

def gcd(a, b):
	while 1:
		if b == 0:
			return a
		a %= b
		if a == 0:
			return b
		b %= a

def fib_mod(n, mod):
	if n <= 2:
		return ((n + 1 >> 1) % mod, (n + 2 >> 1) % mod)
	mask = 4
	while mask <= n:
		mask <<= 1
	mask >>= 2
	(a, b) = (1, 1)
	while mask:
		if mask & n:
			(a, b) = ((a * a + b * b) % mod, b * ((a << 1) + b) % mod)
		else:
			(a, b) = (a * ((b << 1) - a) % mod, (a * a + b * b) % mod)
		mask >>= 1
	return (a, b)

def divisors(n):
	l = [1]
	f = factors(n)
	for (p, e) in f:
		for i in range(len(l)):
			v = l[i]
			for j in range(e):
				v *= p
				l.append(v)
	return sorted(l)

def p6():

	def solve(seq):
		seq = sorted(seq)
		next = []
		for i in range(len(seq)):
			for j in range(i + 1, len(seq)):
				if seq[j] % seq[i] == 0:
					break
			else:
				next.append(seq[i])
		seq = next[:]
		ans = 1
		for i in range(len(seq)):
			c = seq[i]
			ans = ans * fib_mod(c, MOD)[0] % MOD
			t = 1
			s = set()
			for g in seq[:i]:
				s.add(gcd(g, c))
			s = list(sorted(s))
			k = solve(s)
			ans = ans * pow(k, MOD - 2, MOD) % MOD
		return ans
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	seq = []
	for _ in range(T):
		N = int(stdin.readline())
		seq.append(N)
	print(solve(seq))
p6()


import sys, random
from math import sqrt

def gcd(a, b):
	while 1:
		if b == 0:
			return a
		a %= b
		if a == 0:
			return b
		b %= a

def fib_mod(n, mod):
	if n <= 2:
		return ((n + 1 >> 1) % mod, (n + 2 >> 1) % mod)
	mask = 4
	while mask <= n:
		mask <<= 1
	mask >>= 2
	(a, b) = (1, 1)
	while mask:
		if mask & n:
			(a, b) = ((a * a + b * b) % mod, b * ((a << 1) + b) % mod)
		else:
			(a, b) = (a * ((b << 1) - a) % mod, (a * a + b * b) % mod)
		mask >>= 1
	return (a, b)

def divisors(n):
	l = [1]
	f = factors(n)
	for (p, e) in f:
		for i in range(len(l)):
			v = l[i]
			for j in range(e):
				v *= p
				l.append(v)
	return sorted(l)

def p6():

	def solve(seq):
		seq = sorted(seq)
		next = []
		for i in range(len(seq)):
			for j in range(i + 1, len(seq)):
				if seq[j] % seq[i] == 0:
					break
			else:
				next.append(seq[i])
		seq = next[:]
		ans = 1
		for i in range(len(seq)):
			c = seq[i]
			ans = ans * fib_mod(c, MOD)[0] % MOD
			t = 1
			s = set()
			for g in seq[:i]:
				s.add(gcd(g, c))
			s = list(sorted(s))
			k = solve(s)
			ans = ans * pow(k, MOD - 2, MOD) % MOD
		return ans
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	seq = []
	for _ in range(T):
		N = int(stdin.readline())
		seq.append(N)
	print(solve(seq))
p6()


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

def matrix_mul(A, B, p=10 ** 9 + 7):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p]]

def matrix_pow(A, n, p=10 ** 9 + 7):
	if n == 0:
		return [[1, 0], [0, 1]]
	B = matrix_pow(A, n // 2, p)
	B = matrix_mul(B, B, p)
	if n % 2 == 1:
		B = matrix_mul(B, A, p)
	return B

def fibonacci(A, B, n, p=10 ** 9 + 7):
	M = matrix_pow([[1, 1], [1, 0]], n, p)
	return (M[1][0] * B + M[1][1] * A) % p

def gcd(a, b):
	rem = a % b
	if rem == 0:
		return b
	return gcd(b, rem)

def fib_lcm(A):
	if len(A) == 1:
		return fibonacci(0, 1, A[0])
	B = list(set([gcd(A[0], a) for a in A[1:]]))
	return fib_lcm(A[1:]) * fibonacci(0, 1, A[0]) * pow(fib_lcm(B), p - 2, p) % p
N = int(input())
A = [int(input()) for _ in range(N)]
print(fib_lcm(A))