Fibonacci numbers have the following form: 

$\begin{aligned}F_1&-1\\ F_2&=1\\ F_3&=2\\ \vdots\\ F_n&=F_{n-2}+F_{n-1}\end{aligned}$  

We have an array $a_1,a_2,\ldots,a_N$ which contains $N$ elements.   

We want to find $\text{gcd}(F_{a_1},F_{a_2},F_{a_3},...,F_{a_N})$.  

Input Format 

The first line contains $N$, where $N$ denotes size of the array. 

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

Output Format 

Print a single integer — the remainder of the division of the resulting number by $10^9+7$.  

Constraints 

$1\leq N\leq2\times10^5$ 

$1\leq a_i\leq10^{12}$  

Sample Input 1

3
2
3
5

Sample Output 1

1

Explanation 1 

$F_{2}=1$ 

$F_3=2$ 

$F_5=5$ 

$\text{gcd}(1,2,5)=1$  

Sample Input 2

2
3
6

Sample Output 2

2

Explanation 2 

$F_3=2$ 

$F_6=8$ 

$\text{gcd}(2,8)=2$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


import sys
from math import sqrt

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 gcd(a, b):
	while 1:
		if b == 0:
			return a
		a %= b
		if a == 0:
			return b
		b %= a

def solve():
	stdin = sys.stdin
	write = sys.stdout.write
	N = int(stdin.readline())
	MOD = 10 ** 9 + 7
	g = 0
	for _ in range(N):
		a = int(stdin.readline())
		g = gcd(a, g)
	write('%d\n' % fib_mod(g, 10 ** 9 + 7)[0])
solve()


LARGE_MOD = 10 ** 9 + 7

def gcd(x, y):
	num1 = x
	num2 = y
	while num1 > 0 and num2 > 0:
		if num1 >= num2:
			num1 = num1 % num2
		else:
			num2 = num2 % num1
	if num1 == 0:
		return num2
	else:
		return num1

def mat_mult(A, B):
	(A[0][0], A[0][1], A[1][0], A[1][1]) = (A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1], A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1])

def mat_mod(A, mod):
	A[0][0] = A[0][0] % mod
	A[0][1] = A[0][1] % mod
	A[1][0] = A[1][0] % mod
	A[1][1] = A[1][1] % mod

def quick_fibonacci(n, mod):
	exponent = n - 1
	A = [[1, 1], [1, 0]]
	current_power_of_A = A
	result = [[1, 0], [0, 1]]
	while exponent > 0:
		if exponent % 2 == 1:
			mat_mult(result, current_power_of_A)
			mat_mod(result, mod)
		exponent = exponent // 2
		mat_mult(current_power_of_A, current_power_of_A)
		mat_mod(current_power_of_A, mod)
	return result[0][0]
curr_gcd = 0
N = int(input())
for c in range(N):
	a = int(input())
	curr_gcd = gcd(curr_gcd, a)
print(quick_fibonacci(curr_gcd, LARGE_MOD))


X = 1000000007

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

def mul(A, B):
	(a, b, c) = A
	(d, e, f) = B
	return ((a * d + b * e) % X, (a * e + b * f) % X, (b * e + c * f) % X)

def pow(A, n):
	if n == 1:
		return A
	if n & 1 == 0:
		return pow(mul(A, A), n // 2)
	else:
		return mul(A, pow(mul(A, A), (n - 1) // 2))

def fib(n):
	if n < 2:
		return n
	return pow((1, 1, 0), n - 1)[0]
N = int(input())
res = int(input())
for i in range(N - 1):
	res = gcd(res, int(input()))
print(fib(res) % X)


import fractions, functools, 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, gcd)[1][0]
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
gcd = functools.reduce(fractions.gcd, A)
print(fibonacci(gcd))


import fractions, functools, 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, gcd)[1][0]
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
gcd = functools.reduce(fractions.gcd, A)
print(fibonacci(gcd))


import fractions
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 solve(array):
	curr_gcd = array[0]
	for number in array[1:]:
		curr_gcd = fractions.gcd(curr_gcd, number)
	return fibonacci(curr_gcd)
n = int(input())
array = [int(input()) for _ in range(n)]
print(solve(array))


import fractions, functools, 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, gcd)[1][0]
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
gcd = functools.reduce(fractions.gcd, A)
print(fibonacci(gcd))


from functools import reduce
MOD = 1000000007

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

def matrix_mult(a, b):
	return [(a[0] * b[0] + a[1] * b[2]) % MOD, (a[0] * b[1] + a[1] * b[3]) % MOD, (a[2] * b[0] + a[3] * b[2]) % MOD, (a[2] * b[1] + a[3] * b[3]) % MOD]
n = int(input())
GCD = int(input())
for _ in range(n - 1):
	GCD = gcd(int(input()), GCD)
exponent = '{0:b}'.format(GCD - 1)
n_powers = len(exponent)
power_table = [0] * n_powers
power_table[0] = [1, 1, 1, 0]
for i in range(1, n_powers):
	power_table[i] = matrix_mult(power_table[i - 1], power_table[i - 1])
mtp = reduce(matrix_mult, [power_table[i] for i in range(n_powers) if exponent[n_powers - i - 1] == '1'], [1, 0, 0, 1])
print(mtp[0] % MOD)


n = int(input().strip())
arr = []
for i in range(n):
	arr.append(int(input().strip()))

def gcd(x, y):
	while y > 0:
		(x, y) = (y, x % y)
	return x
fibonacci = {0: 0, 1: 1, 2: 1}

def fib(n, modulus):
	if n not in fibonacci:
		if n % 2 == 1:
			a = fib(n // 2, modulus)
			b = fib(n // 2 + 1, modulus)
			fibonacci[n] = (a * a + b * b) % modulus
		else:
			a = fib(n // 2, modulus)
			b = fib(n // 2 - 1, modulus)
			c = a + b
			fibonacci[n] = (a * c + b * a) % modulus
	return fibonacci[n]
index_gcd = arr[0]
for i in arr:
	index_gcd = gcd(index_gcd, i)
print(fib(index_gcd, 10 ** 9 + 7))


import fractions

def fibo(n, m1):
	if n == 1:
		return 1
	elif n == 2:
		return 1
	else:
		return (fibo(n - 1, m1) % m1 + fibo(n - 2, m1) % m1) % m1

def matr_dot(m1, m2, m):
	y00 = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % m
	y01 = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % m
	y10 = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % m
	y11 = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % m
	return [[y00, y01], [y10, y11]]

def matrix_pow_mod(A, p, m):
	if p == 1:
		return A
	if p % 2 == 1:
		return matr_dot(A, matrix_pow_mod(A, p - 1, m), m)
	B = matrix_pow_mod(A, p / 2, m)
	return matr_dot(B, B, m)

def fibo3(a, b, n, m):
	if n == 0:
		return a
	if n == 1:
		return b
	f1 = [b, a]
	matrA = [[1, 1], [1, 0]]
	matr1 = matrix_pow_mod(matrA, n - 1, m)
	res = matr1[0][0] * f1[0] + matr1[0][1] * f1[1]
	return res % m
m1 = 1000000007
nn = int(input())
aa = []
for i1 in range(nn):
	ai = int(input())
	aa.append(ai)
k1 = aa[0]
for i1 in range(1, nn):
	k1 = fractions.gcd(k1, aa[i1])
print(fibo3(1, 1, k1 - 1, m1))


MOD = 10 ** 9 + 7
PISANO = 3 if MOD == 2 else 20 if MOD == 5 else MOD - 1 if MOD % 10 == 1 or MOD % 10 == 9 else 2 * (MOD + 1)

def mul22(A, B):
	(a00, a01, a10, a11) = A
	(b00, b01, b10, b11) = B
	return ((a00 * b00 + a01 * b10) % MOD, (a00 * b01 + a01 * b11) % MOD, (a10 * b00 + a11 * b10) % MOD, (a10 * b01 + a11 * b11) % MOD)
F = [(0, 1, 1, 1)]
for i in range(31):
	F.append(mul22(F[-1], F[-1]))

def getFib(n):
	n = n % PISANO
	f = (1, 0, 0, 1)
	for (i, b) in enumerate(reversed('{0:b}'.format(n))):
		if b == '1':
			f = mul22(f, F[i])
	return f[2] % MOD

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b
As = sorted(set((int(input()) for _ in range(int(input())))))
g = 0
for a in As:
	g = gcd(g, a)
print(getFib(g))


from fractions import gcd

def fib(n):
	M = 1000000007
	if n == 1 or n == 2:
		return 1
	if n == 3:
		return 2
	if n % 3 == 0:
		temp = fib(int(n / 3))
		return (5 * temp * temp * temp % M + 3 * temp * pow(-1, int(n / 3)) % M) % M
	elif n % 3 == 1:
		temp1 = fib(int((n - 1) / 3))
		temp2 = fib(int((n - 1) / 3) + 1)
		return (temp2 * temp2 * temp2 % M + 3 * temp2 * temp1 * temp1 % M - temp1 * temp1 * temp1 % M) % M
	else:
		temp1 = fib(int((n - 2) / 3))
		temp2 = fib(int((n - 2) / 3) + 1)
		return (temp2 * temp2 * temp2 % M + 3 * temp1 * temp2 * temp2 % M + temp1 * temp1 * temp1 % M) % M
n = int(input())
gcd_cur = int(input())
for i in range(n - 1):
	if gcd_cur == 1:
		break
	gcd_cur = gcd(int(input()), gcd_cur)
print(fib(gcd_cur))


from fractions import gcd
from functools import reduce
mod = 10 ** 9 + 7
fibs = dict()

def fib(n):
	if n < 2:
		return 1
	if n in fibs:
		return fibs[n]
	fibs[n] = (fib((n + 1) // 2) * fib(n // 2) + fib((n - 1) // 2) * fib((n - 2) // 2)) % mod
	return fibs[n]
print(fib(reduce(lambda x, y: gcd(x, y), (int(input()) for i in range(int(input())))) - 1))


import fractions, functools, 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]
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
gcd = functools.reduce(fractions.gcd, A)
print(fibonacci(gcd))


from functools import reduce

def G(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
(mem, m) = ({0: 1, 1: 1}, 1000000007)

def F(n):
	if n in mem:
		return mem[n]
	k = n // 2
	if n & 1:
		mem[n] = (F(k) * F(k + 1) + F(k - 1) * F(k)) % m
	else:
		mem[n] = (F(k) * F(k) + F(k - 1) * F(k - 1)) % m
	return mem[n]
x = reduce(G, [int(input()) for _ in range(int(input()))])
print(F(x - 1))


MOD = 7 + 10 ** 9

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

def gcdA():
	g = A[0]
	if N == 1:
		return g
	for x in A[1:]:
		g = gcd(g, x)
	return g

def fibonacci(n):
	(v1, v2, v3) = (1, 1, 0)
	for rec in bin(n)[3:]:
		calc = v2 * v2 % MOD
		(v1, v2, v3) = ((v1 * v1 + calc) % MOD, (v1 + v3) * v2 % MOD, (calc + v3 * v3) % MOD)
		if rec == '1':
			(v1, v2, v3) = ((v1 + v2) % MOD, v1, v2)
	return v2

def solve():
	g = gcdA()
	return fibonacci(g)
N = int(input().strip())
A = []
for _ in range(N):
	A.append(int(input().strip()))
print(solve())


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b != 0:
		t = b
		b = a % b
		a = t
	return a
fib_cache = {}

def fib_mod(n):
	mod = 1000000007
	if n <= 2:
		return 1
	if n in fib_cache:
		return fib_cache[n]
	if n % 2 == 0:
		k = n // 2
		fib = (2 * fib_mod(k - 1) + fib_mod(k)) * fib_mod(k)
	else:
		k = (n + 1) // 2
		fib = fib_mod(k) * fib_mod(k) + fib_mod(k - 1) * fib_mod(k - 1)
	fib = fib % mod
	fib_cache[n] = fib
	return fib
n_lines = int(input())
indexes = [None] * n_lines
for i in range(n_lines):
	n = int(input())
	indexes[i] = n
indexes.sort()
prev_val = indexes[0]
index_gcd = indexes[0]
for val in indexes[1:]:
	if val == prev_val:
		continue
	prev_val = val
	index_gcd = gcd(index_gcd, val)
	if index_gcd == 1:
		break
answer = fib_mod(index_gcd)
print(answer)


mod = 10 ** 9 + 7

def fib(n):
	a = b = 1
	c = 0
	s = bin(n)[3:]
	for i in s:
		if i == '1':
			(a, b, c) = (a * (a + (b << 1)) % mod, (a ** 2 + b ** 2) % mod, b * (a + c) % mod)
		else:
			(a, b, c) = ((a ** 2 + b ** 2) % mod, b * (a + c) % mod, (b * b + c * c) % mod)
	return b

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(input())
m = int(input())
for i in range(n - 1):
	m = gcd(m, int(input()))
print(fib(m))


import fractions, functools, 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]
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
gcd = functools.reduce(fractions.gcd, A)
print(fibonacci(gcd))


def F(n):
	if n == 0:
		return n
	i = n - 1
	a = 1
	b = 0
	c = 0
	d = 1
	while i > 0:
		if i % 2 == 1:
			aux1 = (d * b + c * a) % 1000000007
			aux2 = (d * (b + a) + c * b) % 1000000007
			a = aux1
			b = aux2
		aux1 = (c * c + d * d) % 1000000007
		aux2 = d * (2 * c + d) % 1000000007
		c = aux1 % 1000000007
		d = aux2 % 1000000007
		i = i // 2
	return (a + b) % 1000000007

def mcd(a, b):
	if b == 0:
		return a
	else:
		return mcd(b, a % b)
t = int(input())
ans = 0
for i in range(t):
	num = int(input())
	if i == 0:
		ans = num
	else:
		ans = mcd(ans, num)
print(F(ans))


from math import gcd

def fast_fib(n, ans):
	MOD = 10 ** 9 + 7
	if n == 0:
		ans[0] = 0
		ans[1] = 1
		return
	fast_fib(n // 2, ans)
	a = ans[0]
	b = ans[1]
	c = 2 * b - a
	if c < 0:
		c += MOD
	c = a * c % MOD
	d = (a * a + b * b) % MOD
	if not n & 1:
		ans[0] = c
		ans[1] = d
	else:
		ans[0] = d
		ans[1] = c + d
T = int(input())
g = int(input())
for _ in range(T - 1):
	n = int(input())
	if g != 1:
		g = gcd(g, n)
ans = [0, 0]
fast_fib(g, ans)
print(ans[0])


from fractions import gcd
from functools import lru_cache
MAX = 10 ** 9 + 7

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1 or n == 2:
		return 1
	if n & 1:
		return (fib((n + 1) // 2) * fib((n + 1) // 2) + fib((n + 1) // 2 - 1) * fib((n + 1) // 2 - 1)) % MAX
	else:
		return (2 * fib(n // 2 - 1) + fib(n // 2)) * fib(n // 2) % MAX
N = int(input())
s = []
for a in range(N):
	s.append(int(input()))
(mi, ma) = (min(s), max(s))
g = gcd(mi, ma)
g = fib(g)
print(g % MAX)


import sys
from fractions import gcd
from functools import lru_cache
MOD = 10 ** 9 + 7

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % MOD
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % MOD
arr_i = []
n = int(input().strip())
for _ in range(n):
	arr_i.append(int(input()))
gcd_n = gcd(min(arr_i), max(arr_i))
print(fib(gcd_n))


import sys
from fractions import gcd
from functools import reduce, lru_cache
MD = 10 ** 9 + 7

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % MD
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % MD
q = int(input().strip())
ar = []
for i in range(q):
	ar.append(int(input()))
g = gcd(min(ar), max(ar))
print(fib(g))


from fractions import gcd
from functools import reduce, lru_cache
MOD = 10 ** 9 + 7
t = int(input())
fib = []
a = []

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib((n + 1) // 2) * fib((n + 1) // 2) + fib((n + 1) // 2 - 1) * fib((n + 1) // 2 - 1)) % MOD
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % MOD
for i in range(t):
	a.append(int(input()))
g = gcd(min(a), max(a))
print(fib(g) % MOD)


import sys
from time import time

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

def mult(A, B, m):
	C = ((A[0] * B[0] + A[1] * B[2]) % m, (A[0] * B[1] + A[1] * B[3]) % m, (A[2] * B[0] + A[3] * B[2]) % m, (A[2] * B[1] + A[3] * B[3]) % m)
	return C

def solve(aa, m):
	g = aa[0]
	for a in aa:
		g = gcd(a, g)
	print('g=%d' % (g,), file=sys.stderr)
	(M, F) = ((1, 0, 0, 1), (1, 1, 1, 0))
	while g:
		if g % 2 == 1:
			M = mult(M, F, m)
		F = mult(F, F, m)
		g //= 2
	print('M=%s' % (M,), file=sys.stderr)
	return M[1]
tm = time()
t = int(input())
aa = []
for _ in range(t):
	aa.append(int(input()))
m = pow(10, 9) + 7
print(solve(aa, m))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


from fractions import gcd
MOD = 10 ** 9 + 7

def fibonacci(n, cache):
	try:
		return cache[n]
	except KeyError:
		pass
	if n == 1 or n == 2:
		return 1
	k = n // 2
	if n % 2 == 0:
		cache[n] = fibonacci(k, cache) * (fibonacci(k + 1, cache) + fibonacci(k - 1, cache)) % MOD
	else:
		cache[n] = (fibonacci(k + 1, cache) ** 2 + fibonacci(k, cache) ** 2) % MOD
	return cache[n]
n = int(input())
g = 0
for _ in range(n):
	g = gcd(g, int(input()))
cache = {}
print(fibonacci(g, cache))


import fractions

def fibo(n, m1):
	if n == 1:
		return 1
	elif n == 2:
		return 1
	else:
		return (fibo(n - 1, m1) % m1 + fibo(n - 2, m1) % m1) % m1

def matr_dot(m1, m2, m):
	y00 = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % m
	y01 = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % m
	y10 = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % m
	y11 = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % m
	return [[y00, y01], [y10, y11]]

def matrix_pow_mod(A, p, m):
	if p == 1:
		return A
	if p % 2 == 1:
		return matr_dot(A, matrix_pow_mod(A, p - 1, m), m)
	B = matrix_pow_mod(A, p / 2, m)
	return matr_dot(B, B, m)

def fibo3(a, b, n, m):
	if n == 0:
		return a
	if n == 1:
		return b
	f1 = [b, a]
	matrA = [[1, 1], [1, 0]]
	matr1 = matrix_pow_mod(matrA, n - 1, m)
	res = matr1[0][0] * f1[0] + matr1[0][1] * f1[1]
	return res % m
m1 = 1000000007
n = int(input())
aa = []
for i1 in range(n):
	ai = int(input())
	aa.append(ai)
k1 = aa[0]
for i1 in range(1, n):
	k1 = fractions.gcd(k1, aa[i1])
print(fibo3(1, 1, k1 - 1, m1))


from math import gcd
from functools import reduce
mem = {0: 1, 1: 1}
m = 1000000007

def F(n):
	if n in mem:
		return mem[n]
	k = n // 2
	if n & 1:
		mem[n] = (F(k) * F(k + 1) + F(k - 1) * F(k)) % m
	else:
		mem[n] = (F(k) * F(k) + F(k - 1) * F(k - 1)) % m
	return mem[n]
n = int(input())
l = []
for i in range(n):
	l.append(int(input()))
if len(l) > 2:
	g_val = reduce(gcd, l)
elif len(l) == 2:
	g_val = gcd(l[0], l[1])
else:
	g_val = l[0]
res = F(g_val - 1)
print(res)


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


d = {}
d[1] = [[1, 1], [1, 0]]
(k, mod) = (1, 10 ** 9 + 7)
for i in range(1, 60):
	j = k
	x = [[0, 0], [0, 0]]
	(temp1, temp2) = (d[j], d[j])
	x[0][0] = (temp1[0][0] * temp2[0][0] + temp1[0][1] * temp2[1][0]) % mod
	x[0][1] = (temp1[0][0] * temp2[0][1] + temp1[0][1] * temp2[1][1]) % mod
	x[1][0] = (temp1[1][0] * temp2[0][0] + temp1[1][1] * temp2[1][0]) % mod
	x[1][1] = (temp1[1][0] * temp2[0][1] + temp1[1][1] * temp2[1][1]) % mod
	d.update({2 ** i: x})
	k = 2 ** i

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

def getfib(n):
	if n == 1 or n == 2:
		return 1
	n -= 2
	s = bin(n)[2:]
	s = s[::-1]
	temp = []
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '1':
			temp.append(d[2 ** i])
	x = [[0, 0], [0, 0]]
	x[0][0] = temp[0][0][0]
	x[0][1] = temp[0][0][1]
	x[1][0] = temp[0][1][0]
	x[1][1] = temp[0][1][1]
	l = [0] * 4
	for i in range(1, len(temp)):
		l[0] = (x[0][0] * temp[i][0][0] + x[0][1] * temp[i][1][0]) % mod
		l[1] = (x[0][0] * temp[i][0][1] + x[0][1] * temp[i][1][1]) % mod
		l[2] = (x[1][0] * temp[i][0][0] + x[1][1] * temp[i][1][0]) % mod
		l[3] = (x[1][0] * temp[i][0][1] + x[1][1] * temp[i][1][1]) % mod
		(x[0][0], x[0][1], x[1][0], x[1][1]) = (l[0], l[1], l[2], l[3])
	m = (x[0][0] + x[0][1]) % mod
	b = (x[1][0] + x[1][1]) % mod
	return m

def buildTree(tree, arr, index, start, end):
	if start > end:
		return
	if start == end:
		tree[index] = arr[start]
		return
	mid = (start + end) // 2
	buildTree(tree, arr, 2 * index, start, mid)
	buildTree(tree, arr, 2 * index + 1, mid + 1, end)
	g = gcd(tree[2 * index], tree[2 * index + 1])
	tree[index] = g

def query(tree, index, start, end, left, right):
	if start > right or end < left:
		return 0
	if start >= left and end <= right:
		return tree[index]
	mid = (start + end) // 2
	lgcd = query(tree, 2 * index, start, mid, left, right)
	rgcd = query(tree, 2 * index + 1, mid + 1, end, left, right)
	return gcd(lgcd, rgcd)
n = int(input())
arr = []
for i in range(n):
	arr.append(int(input()))
(tree, m) = ([0] * (4 * n + 1), [0] * n)
buildTree(tree, arr, 1, 0, n - 1)
x = query(tree, 1, 0, n - 1, 0, n - 1)
print(getfib(x))


from math import gcd

def mul(a, b, m):
	return ((a[0] * b[0] + a[1] * b[1]) % m, (a[0] * b[1] + a[1] * b[2]) % m, (a[1] * b[1] + a[2] * b[2]) % m)
mod = 10 ** 9 + 7
n = int(input())
g = 0
for i in range(n):
	a = int(input())
	g = gcd(g, a)
x = (1, 1, 0)
y = x if g & 1 else (1, 0, 1)
while g > 1:
	x = mul(x, x, mod)
	g >>= 1
	if g & 1:
		y = mul(x, y, mod)
print(y[1])


import os
import sys
from math import gcd
mod = 1000000007

def multMatrix(A, B):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod, (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod], [(A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod]]

def MatrixPow(A, p):
	if p == 1:
		return A
	res = [[1, 0], [0, 1]]
	while p > 0:
		if p & 1:
			res = multMatrix(res, A)
		A = multMatrix(A, A)
		p >>= 1
	return res

def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	M = [[1, 1], [1, 0]]
	res = MatrixPow(M, n - 1)
	return res[0][0] % mod
n = int(input())
d = int(input())
for i in range(n - 1):
	k = int(input())
	d = gcd(d, k)
print(fib(d))


from fractions import gcd
from functools import reduce, lru_cache
MOD = 10 ** 9 + 7
t = int(input())
fib = []
a = []

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib((n + 1) // 2) * fib((n + 1) // 2) + fib((n + 1) // 2 - 1) * fib((n + 1) // 2 - 1)) % MOD
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % MOD
for i in range(t):
	a.append(int(input()))
g = gcd(min(a), max(a))
print(fib(g) % MOD)


import os
import sys
from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from functools import reduce
from functools import lru_cache

@lru_cache(maxsize=None)
def super_fib(n, m=int(1000000000.0 + 7)):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	elif n > 5 and n % 3 == 0:
		k = n // 3
		return (5 * super_fib(k) ** 3 + 3 * (-1) ** k * super_fib(k)) % m
	elif n > 3 and n % 2 == 0:
		k = n // 2
		return super_fib(k) * (super_fib(k) + 2 * super_fib(k - 1)) % m
	return (super_fib(n - 1) + super_fib(n - 2)) % m

def gcd(a, b):
	assert a > 0 and b > 0
	while b != 0:
		(a, b) = (b, a % b)
	return a

def solve(a):
	pass
n = int(input())
a = []
for _ in range(n):
	a_i = int(input())
	a.append(a_i)
fib_num = reduce(gcd, a)
print(super_fib(fib_num))


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
y = (int(input()) for _ in range(n))
shy = reduce(gcd, y, 0)
print(fib(shy))


P = 10 ** 9 + 7
import os
import sys
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


P = 10 ** 9 + 7
import os
import sys
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


P = 10 ** 9 + 7
from math import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


from math import gcd
from functools import *

@lru_cache(maxsize=None)
def fib(n):
	M = 10 ** 9 + 7
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % M
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % M
n = int(input())
a = [int(input()) for _ in range(n)]
g = reduce(gcd, a, 0)
print(fib(g))


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


P = 10 ** 9 + 7
import os
import sys
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


import math
m = 10 ** 9 + 7

def f(n):
	if n == 0:
		return (0, 1)
	else:
		(a, b) = f(n // 2)
		c = a * (2 * b - a) % m
		d = a * a + b * b % m
		if n % 2 == 0:
			return (c, d)
		else:
			return (d, d + c)
for i in range(int(input())):
	n = int(input())
	if i == 0:
		t = n
		t = math.gcd(t, n)
	else:
		t = math.gcd(t, n)
x = f(t - 1)
print(x[1] % m)


import math
from functools import reduce

def f(n):
	if n == 0:
		return (0, 1)
	else:
		(a, b) = f(n // 2)
		c = a * (2 * b - a) % (10 ** 9 + 7)
		d = (a * a + b * b) % (10 ** 9 + 7)
		if n % 2 == 0:
			return (c, d)
		else:
			return (d, c + d)
l1 = []
for x in range(int(input())):
	l = int(input())
	l1.append(l)
a = reduce(math.gcd, l1, 0)
print(f(a - 1)[1] % (10 ** 9 + 7))


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


import math
from functools import reduce

def f(n):
	if n == 0:
		return (0, 1)
	else:
		(a, b) = f(n // 2)
		c = a * (2 * b - a) % (10 ** 9 + 7)
		d = (a * a + b * b) % (10 ** 9 + 7)
		if n % 2 == 0:
			return (c, d)
		else:
			return (d, c + d)
l1 = []
for x in range(int(input())):
	l = int(input())
	l1.append(l)
a = reduce(math.gcd, l1, 0)
print(f(a - 1)[1] % (10 ** 9 + 7))


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


import sys, math

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(n):
	MOD = 10 ** 9 + 7
	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 fibogcd(a):
	n = len(a)
	g = a[0]
	for i in range(1, n):
		g = math.gcd(g, a[i])
	return fibo(g)

def main():
	n = int(sys.stdin.readline())
	a = []
	for _ in range(n):
		ai = int(sys.stdin.readline())
		a.append(ai)
	print(fibogcd(a))
main()


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd

def matmul(a, b, res):
	result = [[0, 0], [0, 0]]
	result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0]
	result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1]
	result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0]
	result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1]
	for i in range(2):
		for j in range(2):
			res[i][j] = result[i][j] % (10 ** 9 + 7)

def nthFibonacci(n):
	if n <= 1:
		return n
	base = [[1, 1], [1, 0]]
	result = [[1, 0], [0, 1]]
	while n > 0:
		if n & 1 == 1:
			matmul(base, result, result)
		matmul(base, base, base)
		n >>= 1
	return result[0][1]
n = int(input())
g = 0
for i in range(n):
	g = gcd(g, int(input()))
print(nthFibonacci(g))


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


P = 10 ** 9 + 7
from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize=None)
def fib(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n & 1 == 1:
		return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
	else:
		return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])


from math import gcd
p = 1000000007

def fib(n):
	(a, b) = (0, 1)
	for bt in bin(n)[2:]:
		(a, b) = (a * (a + 2 * b) % p, (a * a + b * b) % p)
		if bt == '1':
			(a, b) = (a + b, a)
	return a % p
(N, *A) = open(0).read().split()
res = 0
for a in A:
	res = gcd(int(a), res)
print(fib(res))


from math import gcd
MOD = 1000000007

def multm(A, B):
	(a00, a10, a01, a11) = A
	(b00, b10, b01, b11) = B
	return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD, (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]

def multv(A, V):
	(a00, a10, a01, a11) = A
	(b0, b1) = V
	return [(a00 * b0 + a10 * b1) % MOD, (a01 * b0 + a11 * b1) % MOD]

def power(M, k):
	P = [1, 0, 0, 1]
	if k == 0:
		return P
	if k == 1:
		return M
	while k != 0:
		if k % 2 == 1:
			P = multm(P, M)
		M = multm(M, M)
		k //= 2
	return P
g = 0
n = int(input())
for i in range(n):
	g = gcd(g, int(input()))
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])