Given an equation of the form f(n) = f(n-1) + f(n-2) where f(0) = 1, f(1) = 1 , the task is to find the n^{th} term of this sequence.
 
Example 1:
Input: n = 3
Output: 3
Explanation: f(3) = f(2) + f(1) = 3
Example 2:
Input: n = 2
Output: 2
Explanation: f(2) = f(1) + f(0) = 2
 
Yout Task:
You don't need to read or print anything. Your task is to complete the function FindNthTerm() which takes n as input parameter and returns n^{th} term mod 10^9+7 .
Expected Time Complexity: O(log(n))
Expected Space Complexity: O(K) where K is constant.
 
Constraints:
1 <= n <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

Number theory

Starter code: #User function Template for python3



class Solution:

	def FindNthTerm(self, n):

		# Code here

Solutions:
class Solution:

	def multiply(self, a, b):
		mul = [[0 for x in range(3)] for y in range(3)]
		for i in range(3):
			for j in range(3):
				mul[i][j] = 0
				for k in range(3):
					mul[i][j] += a[i][k] * b[k][j]
		for i in range(3):
			for j in range(3):
				a[i][j] = mul[i][j] % int(1000000000.0 + 7)
		return a

	def power(self, F, n):
		M = [[1, 1, 0], [1, 0, 0], [0, 1, 0]]
		if n == 1:
			return F[0][0] + F[0][1]
		self.power(F, int(n / 2))
		F = self.multiply(F, F)
		if n % 2 != 0:
			F = self.multiply(F, M)
		return F[0][0] + F[0][1]

	def FindNthTerm(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		F = [[1, 1, 0], [1, 0, 0], [0, 1, 0]]
		k = self.power(F, n - 1)
		return k % int(1000000000.0 + 7)


def matMult(mat1, mat2):
	return [[(mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0]) % 1000000007, (mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]) % 1000000007], [(mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0]) % 1000000007, (mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1]) % 1000000007]]

def solver(n, dct):
	if n == 0:
		return [[1, 1], [1, 0]]
	elif n == 1:
		return [[1, 1], [1, 0]]
	elif n == 2:
		return [[2, 1], [1, 1]]
	if n in dct:
		return dct[n]
	mat = [[1, 1], [1, 0]]
	if n % 2 == 0:
		mat = matMult(solver(n // 2, dct), solver(n // 2, dct))
	else:
		mat = matMult(solver(n // 2, dct), solver(n // 2 + 1, dct))
	dct[n] = mat
	return mat

class Solution:

	def FindNthTerm(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		dct = dict()
		mat = solver(n, dct)
		return mat[0][0]


class Solution:

	def FindNthTerm(self, N):

		def multiply(F, M):
			mod = 10 ** 9 + 7
			x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
			y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
			z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
			w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
			F[0][0] = x % mod
			F[0][1] = y % mod
			F[1][0] = z % mod
			F[1][1] = w % mod

		def power(F, n):
			if n == 0 or n == 1:
				return
			M = [[1, 1], [1, 0]]
			power(F, n // 2)
			multiply(F, F)
			if n % 2 != 0:
				multiply(F, M)
		mod = 10 ** 9 + 7
		if n == 0 or n == 1:
			return 1
		F = [[1, 1], [1, 0]]
		power(F, n - 1)
		return (F[0][0] % mod + F[0][1] % mod) % mod


import numpy as np
M = 10 ** 9 + 7

def exp(m, n):
	ans = np.eye(2, dtype=np.int_)
	while n:
		if n & 1:
			ans = ans @ m % M
		m = m @ m % M
		n >>= 1
	return ans % M

class Solution:

	def FindNthTerm(self, n):
		m = np.array([1, 1, 1, 0], dtype=np.int_).reshape(2, 2)
		p = exp(m, n - 1)
		init = np.array([1, 1], dtype=np.int_).reshape(2, 1)
		return (p @ init)[0][0] % M


class Solution:

	def Multiply(self, a, b, mod):
		multiply = [[0, 0], [0, 0]]
		multiply[0][0] = (a[0][0] * b[0][0] % mod + a[0][1] * b[1][0] % mod) % mod
		multiply[0][1] = (a[0][0] * b[0][1] % mod + a[0][1] * b[1][1] % mod) % mod
		multiply[1][0] = (a[1][0] * b[0][0] % mod + a[1][1] * b[1][0] % mod) % mod
		multiply[1][1] = (a[1][0] * b[0][1] % mod + a[1][1] * b[1][1] % mod) % mod
		return multiply

	def GetAnswer(self, matrix, n, mod):
		if n == 0:
			ans = [[1, 0], [0, 1]]
			return ans
		elif n % 2 == 0:
			ans = self.GetAnswer(matrix, n // 2, mod)
			return self.Multiply(ans, ans, mod)
		else:
			ans = self.GetAnswer(matrix, n - 1, mod)
			return self.Multiply(matrix, ans, mod)

	def FindNthTerm(self, n):
		mod = 1000000007
		matrix = [[0, 1], [1, 1]]
		ans = self.GetAnswer(matrix, n, mod)
		return ans[1][1] % mod


class Solution:

	def multiply(self, a, b):
		c = []
		for i in range(2):
			d = []
			for j in range(2):
				g = 0
				for k in range(2):
					g += a[i][k] * b[k][j] % 1000000007
				d.append(g)
			c.append(d)
		return c

	def mat_expo(self, a, n):
		if n == 0:
			return [[1, 0], [0, 1]]
		if n == 1:
			return [[1, 1], [1, 0]]
		temp = self.mat_expo(a, n // 2)
		ans = self.multiply(temp[:], temp[:])
		if n % 2 == 1:
			ans = self.multiply(ans[:], [[1, 1], [1, 0]])
		return ans

	def FindNthTerm(self, n):
		if n <= 2:
			return n
		a = [[1, 1], [1, 0]]
		b = self.mat_expo(a, n - 1)
		g = b[0][0] + b[0][1]
		return g % 1000000007


class Solution:

	def helper(self, n):
		M = 10 ** 9 + 7
		if n == 0:
			return [0, 1]
		p = self.helper(n // 2)
		c = (2 * p[0] * p[1] % M - p[0] * p[0] % M) % M
		d = (p[0] * p[0] % M + p[1] * p[1] % M) % M
		if n & 1:
			return [d, (c + d) % M]
		else:
			return [c, d]

	def FindNthTerm(self, n):
		return self.helper(n + 1)[0]


class Solution:
	FIBMAT = [[0, 1], [1, 1]]
	ID2 = [[1, 0], [0, 1]]
	MOD = 10 ** 9 + 7

	@staticmethod
	def matmul(m1, m2, MOD=MOD):
		return [[sum((m1[i][k] * m2[k][j] for k in range(len(m2)))) % MOD for j in range(len(m2[1]))] for i in range(len(m1))]

	@staticmethod
	def matpow(base, exp):
		bpow = base
		bexp = 1
		result = Solution.ID2
		while bexp <= exp:
			if exp & bexp:
				result = Solution.matmul(result, bpow)
			bpow = Solution.matmul(bpow, bpow)
			bexp += bexp
		return result

	def FindNthTerm(self, n):
		mat = Solution.matpow(Solution.FIBMAT, n)
		return sum(mat[0]) % Solution.MOD
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.FindNthTerm(n)
		print(ans)


class Solution:

	def FindNthTerm(self, n):
		m = 1000000007
		if n < 2:
			return 1
		mt = [[1, 1], [1, 0]]
		f = [[1], [1]]

		def mul(A, B):
			res = [[0, 0], [0, 0]]
			for i in range(len(A)):
				for j in range(len(B[0])):
					for k in range(len(B)):
						res[i][j] += A[i][k] * B[k][j]
						res[i][j] %= m
			return res

		def exp(n):
			if n == 1:
				return mt
			h = n // 2
			ans = exp(h)
			ans = mul(ans, ans)
			if n % 2 == 0:
				return ans
			else:
				ans = mul(ans, mt)
				return ans
		s = exp(n - 1)
		mxl = mul(s, f)
		return mxl[0][0] % m
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.FindNthTerm(n)
		print(ans)


from typing import List

class Solution:

	def matrixMultiplication(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
		MOD = 1000000007
		dim = len(mat1)
		res = [[0] * dim for _ in range(dim)]
		for i in range(dim):
			for j in range(dim):
				for k in range(dim):
					res[i][j] = (res[i][j] + mat1[i][k] % MOD * (mat2[k][j] % MOD) % MOD) % MOD
		return res

	def getIdentityMatrix(self, dim):
		res = [[0] * dim for _ in range(dim)]
		for i in range(dim):
			res[i][i] = 1
		return res

	def matrixExpo(self, matrix: List[List[int]], power: int) -> List[List[int]]:
		dim = len(matrix)
		result = self.getIdentityMatrix(dim)
		while power > 0:
			if power & 1:
				result = self.matrixMultiplication(result, matrix)
				power -= 1
			else:
				matrix = self.matrixMultiplication(matrix, matrix)
				power = power >> 1
		return result

	def FindNthTerm(self, n):
		if n == 0:
			return 0
		mat = self.matrixExpo([[0, 1], [1, 1]], n)
		return mat[1][1]


class Solution:

	def FindNthTerm(self, n):
		if n == 1:
			return 1
		if n == 0:
			return 1
		intial = [[1], [1]]
		A = [[1, 1], [1, 0]]

		def mul_matrix(a, b):
			res = [[0, 0], [0, 0]]
			for i in range(len(a)):
				for j in range(len(b[0])):
					for k in range(len(b)):
						res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % (10 ** 9 + 7)
			return res

		def mat_exp(n, A):
			if n == 1:
				return A
			ans = mat_exp(n // 2, A)
			ans = mul_matrix(ans, ans)
			if n % 2 == 0:
				return ans
			else:
				ans = mul_matrix(ans, A)
				return ans
		x = mat_exp(n - 1, A)
		final = mul_matrix(x, intial)
		return final[0][0]


class Solution:

	def FindNthTerm(self, n):

		def mul(mat1, mat2):
			ans = [[0, 0], [0, 0]]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						ans[i][j] += mat1[i][k] * mat2[k][j] % 1000000007
			return ans

		def find_nth(a, n):
			if n == 1:
				return a
			ans = find_nth(a, n // 2)
			if n % 2 == 0:
				return mul(ans, ans)
			else:
				return mul(ans, mul(ans, a))
		a = [[1, 1], [1, 0]]
		ans = find_nth(a, n)
		return ans[0][0] % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.FindNthTerm(n)
		print(ans)


class Solution:

	def FindNthTerm(self, n):

		def mul(mat1, mat2):
			ans = [[0, 0], [0, 0]]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						ans[i][j] += mat1[i][k] * mat2[k][j] % 1000000007
			return ans

		def find_nth(a, n):
			if n == 1:
				return a
			ans = find_nth(a, n // 2)
			if n % 2 == 0:
				return mul(ans, ans)
			else:
				return mul(ans, mul(ans, a))
		a = [[1, 1], [1, 0]]
		ans = find_nth(a, n)
		return ans[0][0] % 1000000007


class Solution:

	def FindNthTerm(self, n):
		if n == 1:
			return 1
		power = n
		M = [[1, 1], [1, 0]]
		res = [[1, 1], [1, 0]]
		res = self.power(res, power)
		return res[0][0]

	def power(self, res, power):
		if power == 1:
			return [[1, 1], [1, 0]]
		temp = self.power(res, power // 2)
		temp2 = self.mul(temp, temp)
		if power & 1:
			temp2 = self.mul(temp2, [[1, 1], [1, 0]])
		return temp2

	def mul(self, t1, t2):
		mod = 1000000007
		res = [[1, 1], [1, 0]]
		res[0][0] = (t1[0][0] * t2[0][0] + t1[0][1] * t2[1][0]) % mod
		res[0][1] = (t1[0][0] * t2[1][0] + t1[0][1] * t2[1][1]) % mod
		res[1][0] = (t1[1][0] * t2[0][0] + t1[1][1] * t2[1][0]) % mod
		res[1][1] = (t1[1][0] * t2[1][0] + t1[1][1] * t2[1][1]) % mod
		return res


MOD = 1000000007

class Solution:

	def FindNthTerm(self, n):

		def FastDoubling(n):
			if n == 0:
				return [0, 1]
			res = FastDoubling(n // 2)
			c = (2 * res[0] * res[1] % MOD - res[0] * res[0] % MOD + MOD) % MOD
			d = (res[0] * res[0] % MOD + res[1] * res[1] % MOD) % MOD
			if n & 1:
				return [d, (c + d) % MOD]
			else:
				return [c, d]
		return FastDoubling(n + 1)[0]
		return res[0]


mod = 10 ** 9 + 7

class Solution:

	def Mult(self, A, B):
		n = 2
		C = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(n):
				C[i][j] = sum([A[i][k] * B[k][j] % mod for k in range(n)]) % mod
		return C

	def Expo(self, A, b):
		if b == 0:
			return [[1, 0], [0, 1]]
		if b % 2 == 0:
			p = self.Expo(A, b // 2)
			return self.Mult(p, p)
		return self.Mult(A, self.Expo(A, b - 1))

	def FindNthTerm(self, n):
		if n == 0:
			return 1
		if n == 1:
			return 1
		A = [[0, 1], [1, 1]]
		P = self.Expo(A, n - 1)
		return (P[1][0] + P[1][1]) % mod


class Solution:

	def FindNthTerm(self, n):

		def prod(x, y, m):
			z = [[], []]
			z[0].append(x[0][0] * y[0][0] + x[1][0] * y[0][1])
			z[1].append(x[0][0] * y[1][0] + x[1][0] * y[1][1])
			z[0].append(x[0][1] * y[0][0] + x[1][1] * y[0][1])
			z[1].append(x[0][1] * y[1][0] + x[1][1] * y[1][1])
			z[0][0] = z[0][0] % m
			z[0][1] = z[0][1] % m
			z[1][0] = z[1][0] % m
			z[1][1] = z[1][1] % m
			return z
		x = [[1, 1], [1, 0]]

		def power(x, y, m):
			if y == 1:
				result = x
			else:
				z = y
				w = []
				while z > 0:
					if z % 2 == 0:
						w.append(0)
					else:
						w.append(1)
					z = z // 2
				p = [[1, 0], [0, 1]]
				a = x[:]
				for i in range(0, len(w)):
					if w[i] == 1:
						p = prod(p, a, m)
					a = prod(a, a, m)
				result = p[:]
			return result
		m = 10 ** 9 + 7
		c = power(x, n + 1, m)
		res = c[0][1]
		return res


from numpy import array, int64, matmul

class Solution:

	def FindNthTerm(self, n):
		self.originalMatrix = array([[0, 1], [1, 1]], dtype=int64)
		self.powMatrix = self.originalMatrix.copy()
		self.mod = 10 ** 9 + 7
		self.power(n)
		return self.powMatrix[1][1]

	def power(self, n):
		if n == 0 or n == 1:
			return
		self.power(n // 2)
		self.powMatrix = self.multiply(self.powMatrix, self.powMatrix)
		if n % 2 != 0:
			self.powMatrix = self.multiply(self.powMatrix, self.originalMatrix)

	def multiply(self, m1, m2):
		m = matmul(m1, m2)
		if m[1][1] >= self.mod:
			m %= self.mod
		return m


class Solution:

	def FindNthTerm(self, n):
		a = [[1, 1], [1, 0]]

		def multiply(mat1, mat2):
			ans = [[0, 0], [0, 0]]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						ans[i][j] = ans[i][j] + mat1[i][k] * mat2[k][j] % 1000000007
			return ans

		def check(a, n):
			if n == 1:
				return a
			temp = check(a, n // 2)
			if n % 2 == 0:
				return multiply(temp, temp)
			return multiply(temp, multiply(temp, a))
		m = check(a, n)
		return m[0][0] % 1000000007


MOD = 10 ** 9 + 7

class Solution:
	T = [[0, 1], [1, 1]]

	def multiply(self, A, B):
		C = [[0, 0], [0, 0]]
		C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD
		C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD
		C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD
		C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD
		return C

	def calcule(self, X, n):
		if n == 1:
			return X
		elif n % 2 == 0:
			X = self.calcule(X, n / 2)
			return self.multiply(X, X)
		else:
			return self.multiply(X, self.calcule(X, n - 1))

	def FindNthTerm(self, n):
		if n < 2:
			return 1
		T = self.calcule(self.T, n - 1)
		Fn = [0, 0]
		Fn[0] = T[0][0] + T[0][1]
		Fn[1] = T[1][0] + T[1][1]
		return Fn[1] % MOD


class Solution:

	def matrix_mul(self, a, b):
		mod = 10 ** 9 + 7
		ans = [[0 for _ in range(len(a))] for _ in range(len(a))]
		for i in range(len(a)):
			for j in range(len(a)):
				for k in range(len(a)):
					ans[i][j] += a[i][k] % mod * (b[k][j] % mod) % mod
		return ans

	def matrix_exponentiation(self, a, power):
		if power == 1:
			return a
		root = self.matrix_exponentiation(a, power // 2)
		if power % 2 == 0:
			return self.matrix_mul(root, root)
		else:
			inter = self.matrix_mul(root, root)
			return self.matrix_mul(inter, a)

	def FindNthTerm(self, n):
		if n == 0:
			return 1
		if n == 1:
			return 1
		matrix = [[1, 1], [1, 0]]
		ans_matrix = self.matrix_exponentiation(matrix, n - 1)
		return sum(ans_matrix[0]) % (10 ** 9 + 7)


class Solution:

	def FindNthTerm(self, n):
		m = 10 ** 9 + 7

		def multi(mat, ans):
			res = [[0, 0], [0, 0]]
			for i in range(len(mat)):
				for j in range(len(ans)):
					for k in range(len(mat)):
						res[i][j] += mat[i][k] % m * (ans[k][j] % m)
			return res
		mat = [[1, 1], [1, 0]]
		ans = [[1, 1], [1, 0]]
		while n:
			if n & 1:
				ans = multi(mat, ans)
				n -= 1
			else:
				mat = multi(mat, mat)
				n >>= 1
		return ans[0][1] % m


class Solution:

	def matmul(self, a, b, mod):
		c = [[0 for j in range(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] = (c[i][j] + a[i][k] * b[k][j]) % mod
		return c

	def matexp(self, a, n, mod):
		r = [[1, 0], [0, 1]]
		while n:
			if n & 1:
				r = self.matmul(r, a, mod)
			a = self.matmul(a, a, mod)
			n >>= 1
		return r

	def FindNthTerm(self, n):
		mod = 10 ** 9 + 7
		a = [[1, 1], [1, 0]]
		result = self.matexp(a, n - 1, mod)
		return (result[0][0] + result[0][1]) % mod


class Solution:

	def FindNthTerm(self, n):

		def multiply(a, b):
			m = [[0, 0], [0, 0]]
			m[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % 1000000007
			m[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % 1000000007
			m[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % 1000000007
			m[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % 1000000007
			return m

		def power(a, n):
			if n == 0:
				return [[1, 0], [0, 1]]
			elif n == 1:
				return a
			p = power(a, n // 2)
			if n % 2 == 0:
				return multiply(p, p)
			else:
				p = multiply(p, p)
				return multiply(a, p)

		def function(n):
			if n == 1:
				return 1
			elif n == 2:
				return 2
			m = power([[0, 1], [1, 1]], n)
			z = [[0], [1]]
			return m[1][0] * z[0][0] + m[1][1] * z[1][0]
		return function(n) % 1000000007


MOD = 1000000007

class Solution:

	def multiply_matrix(self, matrix1, matrix2):
		res = [[0, 0], [0, 0]]
		for i in range(2):
			for j in range(2):
				for k in range(2):
					res[i][j] += matrix1[i][k] * matrix2[k][j]
					res[i][j] %= MOD
		return res

	def power(self, exponent):
		res = [[1, 0], [0, 1]]
		c_matrix = [[1, 1], [1, 0]]
		while exponent:
			if exponent % 2:
				res = self.multiply_matrix(res, c_matrix)
			exponent = exponent // 2
			c_matrix = self.multiply_matrix(c_matrix, c_matrix)
		return res

	def f(self, n):
		res = self.power(n)
		return res[0][0]

	def FindNthTerm(self, n):
		return self.f(n)


import math

class Solution:

	def FindNthTerm(self, n):
		m = 10 ** 9 + 7

		def matrix(a, b):
			c = [[0, 0], [0, 0]]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						c[i][j] += a[i][k] * b[k][j] % m
			return c
		mat = [[1, 1], [1, 0]]
		res = [[1, 1], [1, 0]]
		while n:
			if n % 2 != 0:
				res = matrix(mat, res)
			mat = matrix(mat, mat)
			n >>= 1
		return res[0][1] % m


class Solution:

	def FindNthTerm(self, n):
		mod = 10 ** 9 + 7

		def power(M, n1):
			temp = [[1, 1], [1, 0]]
			if n1 == 1:
				return M
			M1 = power(M, int(n1 / 2))
			if n1 % 2 == 0:
				return multiply(M1, M1)
			return multiply(multiply(M1, M1), temp)

		def multiply(a, b):
			mul = [[0 for x in range(2)] for y in range(2)]
			for i in range(2):
				for j in range(2):
					mul[i][j] = 0
					for k in range(2):
						mul[i][j] += a[i][k] * b[k][j]
					mul[i][j] = mul[i][j] % mod
			for i in range(2):
				for j in range(2):
					a[i][j] = mul[i][j]
			return a
		matrix = [[1, 1], [1, 0]]
		arr = power(matrix, n)
		return arr[0][0]


class Solution:

	def FindNthTerm(self, n):
		n += 1
		mod = 10 ** 9 + 7
		if n == 1:
			return 1
		if n == 2:
			return 1
		I = [[0, 0, 0], [0, 1, 0], [0, 0, 1]]
		T = [[0, 0, 0], [0, 0, 1], [0, 1, 1]]
		n -= 1

		def mul(A, B, dim):
			res = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
			for i in range(1, dim + 1):
				for j in range(1, dim + 1):
					for k in range(1, dim + 1):
						temp = A[i][k] * B[k][j] % mod
						res[i][j] = (res[i][j] + temp) % mod
			for i in range(dim + 1):
				for j in range(dim + 1):
					A[i][j] = res[i][j]
		while n:
			if n % 2:
				mul(I, T, 2)
				n -= 1
			else:
				mul(T, T, 2)
				n //= 2
		ans = (1 * I[1][1] + 1 * I[2][1]) % mod
		return ans


class Solution:

	def FindNthTerm(self, n):
		mat = [[1, 1], [1, 0]]
		return self.find_nth(mat, n)[0][0] % 1000000007

	def find_nth(self, mat, n):
		if n == 1:
			return mat
		temp = self.find_nth(mat, n // 2)
		if n & 1:
			return self.multiply_mat(temp, self.multiply_mat(temp, mat))
		else:
			return self.multiply_mat(temp, temp)

	def multiply_mat(self, a, b):
		new_mat = [[0, 0], [0, 0]]
		for i in range(2):
			for j in range(2):
				for k in range(2):
					new_mat[i][j] += a[i][k] * b[k][j] % 1000000007
		return new_mat


class Solution:

	def multiply(self, a, b):
		ans1 = [[0, 0], [0, 0]]
		for i in range(2):
			for j in range(2):
				for k in range(2):
					ans1[i][j] += a[i][k] % 1000000007 * b[k][j] % 1000000007 % 1000000007
		return ans1

	def matrix(self, n, mat):
		if n == 1 or n == 0:
			return mat
		temp = self.matrix(n // 2, mat)
		ans = self.multiply(temp, temp)
		if n % 2 != 0:
			ans = self.multiply(ans, mat)
		return ans

	def FindNthTerm(self, n):
		mat = [[1, 1], [1, 0]]
		res = self.matrix(n, mat)
		return res[0][0] % 1000000007


import numpy as np
mod = 10 ** 9 + 7

class Solution:

	def multiply_matrix(self, mat1, mat2):
		return np.matmul(mat1, mat2) % mod

	def nthPower(self, mat, n):
		if n == 1:
			return mat
		temp = self.nthPower(mat, int(n // 2))
		value = self.multiply_matrix(temp, temp)
		if n % 2 == 0:
			return value
		else:
			return self.multiply_matrix(value, self.nthPower(mat, 1))

	def FindNthTerm(self, n):
		mat = np.array([[1, 1], [1, 0]])
		return self.nthPower(mat, n)[0][0]


class Solution:

	def multiply(self, a, b):
		mod = 10 ** 9 + 7
		mul = [[0 for x in range(3)] for y in range(3)]
		for i in range(3):
			for j in range(3):
				mul[i][j] = 0
				for k in range(3):
					mul[i][j] = (mul[i][j] + a[i][k] * b[k][j] % mod) % mod
		for i in range(3):
			for j in range(3):
				a[i][j] = mul[i][j]
		return a

	def power(self, F, n):
		mod = 10 ** 9 + 7
		M = [[1, 1, 0], [1, 0, 0], [0, 1, 0]]
		if n == 1:
			return (F[0][0] * 2 + (F[0][1] + F[0][2]) % mod) % mod
		self.power(F, int(n / 2))
		F = self.multiply(F, F)
		if n % 2 != 0:
			F = self.multiply(F, M)
		return (F[0][0] * 2 + (F[0][1] + F[0][2]) % mod) % mod

	def FindNthTerm(self, n):
		if n == 1 or n == 2:
			return n
		F = [[1, 1, 0], [1, 0, 0], [0, 1, 0]]
		try:
			return self.power(F, n - 2)
		except Exception as e:
			print(e)


import numpy as np
for_mod = 10 ** 9 + 7

def help(a, n):
	result = np.array([[1, 0], [0, 1]])
	while n:
		if n % 2 == 1:
			result = result @ a % for_mod
		a = a @ a % for_mod
		n = int(n / 2)
	return result % for_mod

class Solution:

	def FindNthTerm(self, n):
		a = np.array([[1, 1], [1, 0]])
		b = help(a, n - 1)
		c = np.array([[1], [1]])
		return (b @ c)[0][0] % for_mod


class Solution:

	def FindNthTerm(self, n):
		mod = int(1000000000.0 + 7)

		def multiply(a, b):
			arr = [[0, 0], [0, 0]]
			arr[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod
			arr[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod
			arr[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod
			arr[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod
			return arr

		def power(arr, p):
			if p == 1:
				return arr
			temp = power(arr, p // 2)
			if p % 2 == 0:
				return multiply(temp, temp)
			return multiply(multiply(temp, temp), arr)
		arr = [[1, 1], [1, 0]]
		arr = power(arr, n)
		return int(arr[0][0])


def multiply(a, b):
	mul = [[0 for x in range(2)] for y in range(2)]
	for i in range(2):
		for j in range(2):
			mul[i][j] = 0
			for k in range(2):
				mul[i][j] += a[i][k] * b[k][j] % 1000000007
	for i in range(2):
		for j in range(2):
			a[i][j] = mul[i][j]
	return a

def power(F, n):
	M = [[1, 1], [1, 0]]
	if n == 1:
		return (F[0][0] + F[0][1]) % 1000000007
	elif n < 1:
		return n + 1
	power(F, int(n / 2))
	F = multiply(F, F)
	if n % 2 != 0:
		F = multiply(F, M)
	return (F[0][0] + F[0][1]) % 1000000007

class Solution:

	def FindNthTerm(self, m):
		F = [[1, 1], [1, 0]]
		return power(F, m - 1)


def multiplymatrix(mat, mat1):
	h = 10 ** 9 + 7
	temp = [[0, 0], [0, 0]]
	temp[0][0] = mat[0][0] * mat1[0][0] % h + mat[0][1] * mat1[1][0] % h
	temp[0][0] %= h
	temp[0][1] = mat[0][0] * mat1[0][1] % h + mat[0][1] * mat1[1][1] % h
	temp[0][1] %= h
	temp[1][0] = mat[1][0] * mat1[0][0] % h + mat[1][1] * mat1[1][0] % h
	temp[1][0] %= h
	temp[1][1] = mat[1][0] * mat1[0][1] % h + mat[1][1] * mat1[1][1] % h
	temp[1][1] %= h
	mat[0][0] = temp[0][0]
	mat[0][1] = temp[0][1]
	mat[1][0] = temp[1][0]
	mat[1][1] = temp[1][1]

def matrix(n, mat):
	if n == 1:
		return
	matrix(n // 2, mat)
	multiplymatrix(mat, mat)
	m = [[1, 1], [1, 0]]
	if n % 2 != 0:
		multiplymatrix(mat, m)

class Solution:

	def FindNthTerm(self, n):
		if n <= 1:
			return 1
		mat = [[1, 1], [1, 0]]
		matrix(n, mat)
		return mat[0][0]


from math import ceil

class Solution:

	def FindNthTerm(self, n):

		def multiply(a, m):
			w = (a[0][0] * m[0][0] + a[0][1] * m[1][0]) % mod
			x = (a[0][0] * m[0][1] + a[0][1] * m[1][1]) % mod
			y = (a[1][0] * m[0][0] + a[1][1] * m[1][0]) % mod
			z = (a[1][0] * m[0][1] + a[1][1] * m[1][1]) % mod
			a[0][0] = w
			a[0][1] = x
			a[1][0] = y
			a[1][1] = z
		mod = 1000000007
		(m, ans) = ([[1, 1], [1, 0]], [[1, 1], [1, 0]])
		if not n:
			return 0
		while n:
			if n & 1:
				multiply(ans, m)
			multiply(m, m)
			n >>= 1
		return ans[0][1]


mod = 10 ** 9 + 7

class Solution:

	def multiply_matrix(self, mat1, mat2):
		a = (mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0]) % mod
		b = (mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]) % mod
		c = (mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0]) % mod
		d = (mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1]) % mod
		return [[a, b], [c, d]]

	def multiply(self, mat, n):
		if n == 1:
			return mat
		temp = self.multiply(mat, n // 2)
		value = self.multiply_matrix(temp, temp)
		if n % 2 == 0:
			return value
		else:
			return self.multiply_matrix(value, self.multiply(mat, 1))

	def FindNthTerm(self, n):
		mat = [[1, 1], [1, 0]]
		return self.multiply(mat, n)[0][0] % mod


class Solution:

	def FindNthTerm(self, n):
		mod = 1000000007

		def mulmat(a, b):
			x = [[0, 0], [0, 0]]
			for i in range(len(a)):
				for j in range(len(b)):
					for k in range(len(b)):
						x[i][j] += a[i][k] * b[k][j] % mod
			return x

		def matexp(pb, y):
			if y == 1:
				return pb
			half = y >> 1
			x = [[0, 0], [0, 0]]
			x = matexp(pb, half)
			x = mulmat(x, x)
			if y % 2 == 0:
				pass
			else:
				x = mulmat(x, pb)
			return x
		if n <= 1:
			return 1
		base = [[1, 1], [1, 0]]
		ini = [[1, 1], [1, 0]]
		pb = matexp(base, n - 1)
		res = mulmat(pb, ini)
		return int(res[0][0] % mod)


class Solution:

	def mul(self, m1, m2):
		a = [[0, 0], [0, 0]]
		for i in range(2):
			for j in range(2):
				for k in range(2):
					a[i][j] += m1[i][k] * m2[k][j]
				a[i][j] = a[i][j] % (10 ** 9 + 7)
		return a

	def recur(self, n):
		if n == 1:
			return [[1, 1], [1, 0]]
		temp = self.recur(n // 2)
		ans = self.mul(temp, temp)
		if n % 2 != 0:
			ans = self.mul(ans, [[1, 1], [1, 0]])
		return ans

	def FindNthTerm(self, n):
		mod = 10 ** 9 + 7
		c = self.recur(n)
		return c[0][0] % mod


mod = 10 ** 9 + 7
p = [[1, 1], [1, 0]]

def prod(x, y):
	a = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % mod
	b = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % mod
	c = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % mod
	d = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % mod
	x[0][0] = a
	x[0][1] = b
	x[1][0] = c
	x[1][1] = d

def power(mat, n):
	if n < 2:
		return
	power(mat, n // 2)
	prod(mat, mat)
	if n % 2 != 0:
		prod(mat, p)

class Solution:

	def FindNthTerm(self, n):
		if n == 0:
			return 0
		mat = [[1, 1], [1, 0]]
		power(mat, n)
		return mat[0][0]


class Solution:

	def FindNthTerm(self, n):
		m = [[1, 1], [1, 0]]
		t = [[1, 1], [1, 0]]

		def multiply(m1, m2):
			MOD = 10 ** 9 + 7
			n = len(m1)
			w = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]
			x = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]
			y = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]
			z = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]
			(m1[0][0], m1[0][1], m1[1][0], m1[1][1]) = (w % MOD, x % MOD, y % MOD, z % MOD)

		def power(n):
			MOD = 10 ** 9 + 7
			if n == 1 or n == 0:
				return 2
			power(n // 2)
			multiply(m, m)
			if n & 1:
				multiply(m, t)
			return (m[0][0] + m[0][1]) % MOD
		if n <= 1:
			return 1
		return power(n - 1)


class Solution:

	def FindNthTerm(self, n):
		m = 10 ** 9 + 7

		def multiply(F, M):
			x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % m
			y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % m
			z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % m
			w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % m
			F[0][0] = x
			F[0][1] = y
			F[1][0] = z
			F[1][1] = w

		def power(F, n):
			if n < 2:
				return
			power(F, n // 2)
			multiply(F, F)
			if n % 2 != 0:
				multiply(F, [[1, 1], [1, 0]])
		F = [[1, 1], [1, 0]]
		power(F, n)
		return F[0][0]


class Solution:

	def FindNthTerm(self, n):
		C_VAL = 10 ** 9 + 7

		def mat_mul(arr, T):
			a1b1 = arr[0][0] * T[0][0] + arr[0][1] * T[1][0]
			a1b2 = arr[0][0] * T[0][1] + arr[0][1] * T[1][1]
			a2b1 = arr[1][0] * T[0][0] + arr[1][1] * T[1][0]
			a2b2 = arr[1][0] * T[0][1] + arr[1][1] * T[1][1]
			arr[0][0] = a1b1 % C_VAL
			arr[0][1] = a1b2 % C_VAL
			arr[1][0] = a2b1 % C_VAL
			arr[1][1] = a2b2 % C_VAL

		def cal_mat(T, N):
			arr = [[1, 1], [1, 0]]
			while N > 0:
				if N % 2 != 0:
					mat_mul(arr, T)
				N = N >> 1
				mat_mul(T, T)
			return arr
		if n == 1:
			return 1
		elif n == 2:
			return 2
		else:
			T = [[1, 1], [1, 0]]
			arr = cal_mat(T, n - 2)
			return (arr[0][0] + arr[0][1]) % C_VAL


import math

class Solution:

	def FindNthTerm(self, n):
		mod = 10 ** 9 + 7
		if n < 2:
			return 1

		def matrix_prod(a, b):
			temp = [[0] * 2 for _ in range(2)]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						temp[i][j] += a[i][k] * b[k][j] % mod
			return temp

		def matrix_expo(grid, power):
			if power == 1:
				return grid
			temp = matrix_expo(grid, power >> 1)
			temp = matrix_prod(temp, temp)
			if power & 1:
				temp = matrix_prod(temp, grid)
			return temp
		mat = [[1, 1], [1, 0]]
		ans = matrix_expo(mat, n - 1)
		temp = (ans[0][0] + ans[0][1]) % mod
		return temp


class Solution:

	def Multiply(self, A, B, n):
		new_mat = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(n):
				for k in range(n):
					new_mat[i][j] += A[i][k] * B[k][j]
				new_mat[i][j] %= 1000000007
		return new_mat

	def FindNthTerm(self, n):
		if n <= 1:
			return 1
		dp = []
		mat = [[1, 1], [1, 0]]
		base_case = [1, 1]
		dp.append(mat)
		a = 2
		while a <= n - 1:
			dp.append(self.Multiply(dp[-1], dp[-1], 2))
			a *= 2
		n -= 1
		ans = [[1, 0], [0, 1]]
		i = 0
		while n:
			if n % 2 == 1:
				ans = self.Multiply(ans, dp[i], 2)
			n //= 2
			i += 1
		return (ans[0][0] + ans[0][1]) % 1000000007


class Solution:

	def FindNthTerm(self, n):
		mod = 1000000007

		def f(dic, n):
			if n == 0:
				return 0
			if n == 1 or n == 2:
				return 1
			if n in dic:
				return dic[n]
			t = -1
			if n % 2 == 0:
				k = n // 2
				t = f(dic, k) * (2 * f(dic, k - 1) + f(dic, k))
			else:
				k = (n + 1) // 2
				t = f(dic, k) * f(dic, k) + f(dic, k - 1) * f(dic, k - 1)
			t = t % mod
			dic[n] = t
			return t
		dic = dict()
		return f(dic, n + 1)


import numpy as np
M = 1000000007

class Solution:

	def FindNthTerm(self, m):
		if m < 2:
			return 1

		def power(n):
			if n == 1:
				return prod
			n_by_2 = power(n // 2)
			if n % 2 == 0:
				return mult2(n_by_2, n_by_2)
			else:
				return mult2(prod, mult2(n_by_2, n_by_2))

		def mult2(m1, m2):
			result = [[0, 0], [0, 0]]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						result[i][j] += m1[i][k] * m2[k][j] % M
			return result
		ab = [[1, 1]]
		prod = [[1, 1], [1, 0]]
		ans = np.dot(ab, power(n - 1))
		return ans[0][0] % M


class Solution:

	def FindNthTerm(self, ni):
		mati = [[1, 0], [0, 1]]
		mo = int(1000000000.0) + 7

		def multiply(a, b):
			w = (a[0][0] * b[0][0] % mo + a[0][1] * b[1][0] % mo) % mo
			x = (a[0][0] * b[0][1] % mo + a[0][1] * b[1][1] % mo) % mo
			y = (a[1][0] * b[0][0] % mo + a[1][1] * b[1][0] % mo) % mo
			z = (a[1][0] * b[0][1] % mo + a[1][1] * b[1][1] % mo) % mo
			return [[w, x], [y, z]]

		def power(t, n):
			if n == 0:
				return mati
			k = power(t, n // 2)
			if n % 2 != 0:
				return multiply(multiply(k, k), t)
			return multiply(k, k)
		mat = [[1, 1], [1, 0]]
		if ni == 0 or ni == 1:
			return 1
		q = power(mat, ni)
		return q[0][0]


class Solution:

	def multiply(self, F, M):
		x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
		y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
		z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
		w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
		F[0][0] = x % 1000000007
		F[0][1] = y % 1000000007
		F[1][0] = z % 1000000007
		F[1][1] = w % 1000000007

	def FindNthTerm(self, n):
		F = [[1, 1], [1, 0]]
		if n == 0:
			return 0
		self.power(F, n)
		return F[0][0]

	def power(self, F, n):
		if n == 0 or n == 1:
			return
		M = [[1, 1], [1, 0]]
		self.power(F, n // 2)
		self.multiply(F, F)
		if n % 2 != 0:
			self.multiply(F, M)


mod = 1000000007
import math

class Solution:

	def FindNthTerm(self, n):

		def fib(n):
			F = [[1, 1], [1, 0]]
			if n == 0:
				return 0
			power(F, n - 1)
			return F[0][0]

		def multiply(F, M):
			x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
			y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
			z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
			w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
			F[0][0] = x % mod
			F[0][1] = y % mod
			F[1][0] = z % mod
			F[1][1] = w % mod

		def power(F, n):
			if n == 0 or n == 1:
				return
			M = [[1, 1], [1, 0]]
			power(F, n // 2)
			multiply(F, F)
			if n % 2 != 0:
				multiply(F, M)
		return fib(n + 1)


mod = pow(10, 9) + 7

class Solution:

	def multiply(self, a, b):
		x = a[0][0] * b[0][0] + a[0][1] * b[1][0]
		y = a[0][0] * b[0][1] + a[0][1] * b[1][1]
		x1 = a[1][0] * b[0][0] + a[1][1] * b[1][0]
		y1 = a[1][0] * b[0][1] + a[1][1] * b[1][1]
		a[0][0] = x % mod
		a[0][1] = y % mod
		a[1][0] = x1 % mod
		a[1][1] = y1 % mod

	def power(self, f, n):
		if n == 1 or n == 0:
			return
		self.power(f, n // 2)
		self.multiply(f, f)
		if n % 2 != 0:
			m = [[1, 1], [1, 0]]
			self.multiply(f, m)

	def FindNthTerm(self, n):
		if n == 0 or n == 1:
			return n
		f = [[1, 1], [1, 0]]
		self.power(f, n)
		return f[0][0]