Rohan has a special love for the matrices especially for the first element of the matrix. Being good at Mathematics, he also loves to solve the different problem on the matrices. So one day he started to multiply the matrix with the original matrix.  The elements of the original matrix are given by a_{00}=1 , a_{01}=1, a_{10}=1, a_{11}=0.
Given the power of the matrix, n calculate the a^{n} and return the a_{10} element mod 1000000007.
Example 1:
Input: n = 3
Output: 2 
Explanation: Take the cube of the original matrix 
i.e a^{3} and the first element(a_{10}) is 2.
Example 2:
Input: n = 4
Output: 3
Explanation: Take the cube of the original matrix
i.e a^{4} and the first element(a_{10}) is 3.
Your Task:  
You dont need to read input or print anything. Complete the function firstElement() which takes n as input parameter and returns the a_{10} element mod 1000000007.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1<= n <=10^{6}

Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:
    def firstElement (self, n):
        # code here 

Solutions:
class Solution:

	def firstElement(self, n):
		a = 0
		b = 1
		for i in range(2, n + 1):
			c = (a + b) % 1000000007
			a = b
			b = c
		return b


class Solution:

	def firstElement(self, n):
		m = 1000000007
		a = 0
		b = 1
		for _ in range(n):
			(a, b) = (b, (a + b) % m)
		return a


class Solution:

	def firstElement(self, n):
		a = 1
		b = 1
		p = n - 1
		while p:
			t = a
			a = a + b
			b = t
			p -= 1
		return b % (10 ** 9 + 7)


class Solution:

	def firstElement(self, n):
		a = [1, 1, 1]
		for i in range(3, n + 1):
			a.append((a[i - 1] + a[i - 2]) % (10 ** 9 + 7))
		return a[-1]


class Solution:

	def firstElement(self, n):
		mod = 10 ** 9 + 7
		dp = [0] * (n + 1)
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod
		return dp[n]


class Solution:

	def firstElement(self, n):
		(a, b, c, d, e, f, g, h) = (1, 1, 1, 0, 1, 1, 1, 0)
		for i in range(n - 1):
			(e, f, g, h) = (a * e + b * g, a * f + b * h, c * e + d * g, c * f + d * h)
		return g % 1000000007


class Solution:

	def firstElement(self, n):
		(a1, a2, a3, a4, r1, r2, r3, r4) = (1, 1, 1, 0, 1, 1, 1, 0)
		for i in range(n - 1):
			(r1, r2, r3, r4) = (r1 * a1 + r2 * a3, r1 * a2 + r2 * a4, r3 * a1 + r4 * a3, r3 * a2 + r4 * a4)
		return r3 % 1000000007


class Solution:

	def mat_mul(self, arr1, arr2):
		return [[arr1[0][0] * arr2[0][0] + arr1[0][1] * arr2[1][0], arr1[0][0] * arr2[0][1] + arr1[0][1] * arr2[1][1]], [arr1[1][0] * arr2[0][0] + arr1[1][1] * arr2[1][0], arr1[1][0] * arr2[0][1] + arr1[1][1] * arr2[1][1]]]

	def pow_mat(self, arr, n):
		if n == 0:
			return [[1, 0], [0, 1]]
		elif n == 1:
			return [[1, 1], [1, 0]]
		elif n % 2:
			return self.mat_mul(self.mat_mul(self.pow_mat(arr, n // 2), self.pow_mat(arr, n // 2)), arr)
		else:
			return self.mat_mul(self.pow_mat(arr, n // 2), self.pow_mat(arr, n // 2))

	def firstElement(self, n):
		arr = [[1, 1], [1, 0]]
		return self.pow_mat(arr, n)[1][0] % 1000000007


class Solution:

	def firstElement(self, n):
		(a0, a1, a2, a3) = (1, 1, 1, 0)
		(b0, b1, b2, b3) = (1, 1, 1, 0)
		mo = 10 ** 9 + 7
		for _ in range(n - 1):
			(b0, b1, b2, b3) = (b0 * a0 + b1 * a2, b0 * a1 + b1 * a3, b2 * a0 + b3 * a2, b2 * a1 + b3 * a3)
			(b0, b1, b2, b3) = (b0 % mo, b1 % mo, b2 % mo, b3 % mo)
		return b2


class Solution:

	def firstElement(self, n):
		l1 = 1
		l2 = 1
		ans = 1
		mod = 1000000007
		for i in range(2, n):
			ans = l1 + l2
			l2 = l1
			l1 = ans
		return ans % mod


import math

class Solution:

	def firstElement(self, n):
		a = [[1, 1], [1, 0]]
		i = [0] * (n + 1)
		i[1] = 1
		for j in range(2, n + 1):
			i[j] = i[j - 1] + i[j - 2]
		return i[-1] % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.firstElement(n))


class Solution:

	def firstElement(self, n):
		(a, b) = (0, 1)
		for i in range(2, n + 1):
			c = (a + b) % 1000000007
			a = b
			b = c
		return b
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.firstElement(n))


class Solution:

	def firstElement(self, n):
		if n <= 2:
			return 1
		else:
			arr = [0] * n
			arr[0] = 1
			arr[1] = 1
			for i in range(2, n):
				arr[i] = arr[i - 1] + arr[i - 2]
			else:
				return arr[-1] % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.firstElement(n))


class Solution:

	def firstElement(self, n):
		F1 = 1
		F2 = 1
		for i in range(3, n + 1):
			(F2, F1) = (F1 + F2, F2)
		return F2 % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.firstElement(n))


import numpy as np

class Solution:

	def firstElement(self, n):
		x = 0
		y = 1
		for i in range(n):
			res = (x + y) % 1000000007
			y = x
			x = res
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.firstElement(n))


class Solution:

	def firstElement(self, n):
		x = 0
		y = 1
		for i in range(n):
			rex = (x + y) % 1000000007
			y = x
			x = rex
		return rex
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.firstElement(n))


class Solution:

	def firstElement(self, n):
		a10 = 1
		a11 = 0
		res = 0
		for i in range(n - 1):
			temp = a10
			a10 += a11
			a11 = temp
		return a10 % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.firstElement(n))


class Solution:

	def firstElement(self, n):
		a = b = 1
		p = 1
		while p < n:
			c = a + b
			b = a
			a = c
			p += 1
		return b % 1000000007


class Solution:

	def firstElement(self, n):

		def mul(mat, m):
			temp = [[0, 0], [0, 0]]
			x = 1000000007
			temp[0][0] = mat[0][0] * m[0][0] + mat[0][1] * m[1][0]
			temp[0][1] = mat[0][0] * m[0][1] + mat[0][1] * m[1][1]
			temp[1][0] = mat[1][0] * m[0][0] + mat[1][1] * m[1][0]
			temp[1][1] = mat[1][0] * m[0][1] + mat[1][1] * m[1][1]
			mat[0][0] = temp[0][0] % x
			mat[0][1] = temp[0][1] % x
			mat[1][0] = temp[1][0] % x
			mat[1][1] = temp[1][1] % x

		def pow_mat(mat, n):
			if n == 1 or n == 0:
				return
			pow_mat(mat, n // 2)
			mul(mat, mat)
			m = [[1, 1], [1, 0]]
			if n % 2 != 0:
				mul(mat, m)
		mat = [[1, 1], [1, 0]]
		pow_mat(mat, n)
		return mat[1][0]


class Solution:

	def firstElement(self, n):

		def mul(mat, m):
			temp = [[0, 0], [0, 0]]
			x = 1000000007
			temp[0][0] = mat[0][0] * m[0][0] + mat[0][1] * m[1][0]
			temp[0][1] = mat[0][0] * m[0][1] + mat[0][1] * m[1][1]
			temp[1][0] = mat[1][0] * m[0][0] + mat[1][1] * m[1][0]
			temp[1][1] = mat[1][0] * m[0][1] + mat[1][1] * m[1][1]
			mat[0][0] = temp[0][0] % x
			mat[0][1] = temp[0][1] % x
			mat[1][0] = temp[1][0] % x
			mat[1][1] = temp[1][1] % x

		def pow_mat(mat, n):
			if n == 1:
				return
			for i in range(2, n):
				m = [[1, 1], [1, 0]]
				mul(mat, m)
		mat = [[1, 1], [1, 0]]
		pow_mat(mat, n)
		return mat[0][0]


class Solution:

	def firstElement(self, n):
		if n == 1 or n == 2:
			return 1
		l = [[1, 1]]
		for i in range(0, n - 2):
			k = l[i][0] * 1 + l[i][1] * 1
			m = l[i][0]
			l.append([k, m])
		return l[len(l) - 1][0] % 1000000007


class Solution:

	def firstElement(self, n):
		a = 1
		b = 1
		if n == 1:
			return 1
		elif n == 2:
			return 1
		ans = 0
		for i in range(2, n):
			ans = a + b
			a = b
			b = ans
		return ans % (10 ** 9 + 7)


class Solution:

	def firstElement(self, n):
		fib = [0, 1]
		for i in range(2, n + 1):
			fib.append(fib[i - 1] + fib[i - 2])
		return fib[n] % 1000000007


class Solution:

	def firstElement(self, n):
		p = 0
		p1 = 1
		mod = 1000000000.0 + 7
		for i in range(2, n + 1):
			c = (p + p1) % mod
			p = p1
			p1 = c
		return int(p1)


class Solution:

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

		def multiply(arr, arr1):
			res = []
			x = arr[0][0] % mod * (arr1[0][0] % mod) + arr[0][1] % mod * (arr1[1][0] % mod)
			y = arr[0][0] % mod * (arr1[0][1] % mod) + arr[0][1] % mod * (arr1[1][1] % mod)
			z = arr[1][0] % mod * (arr1[0][0] % mod) + arr[1][1] % mod * (arr1[1][0] % mod)
			w = arr[1][0] % mod * (arr1[0][1] % mod) + arr[1][1] % mod * (arr1[1][1] % mod)
			arr[0][0] = x % mod
			arr[0][1] = y % mod
			arr[1][0] = z % mod
			arr[1][1] = w % mod

		def solve(arr, n):
			if n == 0 or n == 1:
				return
			f = [[1, 1], [1, 0]]
			solve(arr, n // 2)
			multiply(arr, arr)
			if n % 2 == 1:
				multiply(arr, f)
		arr = [[1, 1], [1, 0]]
		if n == 0:
			return 0
		solve(arr, n)
		return arr[1][0]


class Solution:

	def firstElement(self, N):
		dp = [-1] * (N + 2)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] + dp[i - 2]
		return dp[n] % 1000000007


class Solution:

	def firstElement(self, n):
		if n == 1 or n == 2:
			return 1
		first = 1
		second = 1
		for i in range(2, n):
			third = first + second
			first = second
			second = third
		return second % 1000000007


class Solution:

	def firstElement(self, n):
		mod = 1000000007
		a10 = [0] * (n + 1)
		a10[1] = 1
		for i in range(2, n + 1):
			a10[i] = (a10[i - 1] % mod + a10[i - 2] % mod) % mod
		return a10[n]


class Solution:

	def firstElement(self, n):
		M = 1000000007
		if n <= 1:
			return n
		a = [0] * (n + 1)
		a[1] = 1
		for i in range(2, n + 1):
			a[i] = (a[i - 1] + a[i - 2]) % M
		return a[n]


class Solution:

	def firstElement(self, n):
		(a1, a2, a3, a4) = (1, 1, 1, 0)
		(b1, b2, b3, b4) = (1, 2, 1, 2)
		for i in range(2, n + 1):
			b1 = a1 + a2
			b3 = a3 + a4
			b2 = a1
			b4 = a3
			(a1, a2, a3, a4) = (b1, b2, b3, b4)
		return a3 % 1000000007


class Solution:

	def firstElement(self, n):

		def fibonacci(n):
			f = [0, 1]
			for i in range(2, n + 1):
				f.append(f[i - 1] + f[i - 2])
			return f[n] % 1000000007
		return fibonacci(n)


class Solution:

	def firstElement(self, n):
		one = 0
		two = 1
		f = 1
		for i in range(2, n + 1):
			f = (one + two) % 1000000007
			one = two
			two = f
		return f


class Solution:

	def firstElement(self, n):
		prev1 = 0
		prev2 = 1
		for i in range(2, n + 1):
			curr = prev1 + prev2
			prev1 = prev2
			prev2 = curr
		return prev2 % 1000000007


class Solution:

	def firstElement(self, n):
		a = 0
		b = 1
		i = 1
		if n <= 1:
			return n
		while i != n:
			c = a + b
			a = b
			b = c
			i += 1
		return b % 1000000007


class Solution:

	def firstElement(self, n):
		arr = [-1 for i in range(n)]
		arr[0] = 1
		if n > 1:
			arr[1] = 1
			for j in range(2, n):
				arr[j] = arr[j - 1] + arr[j - 2]
		return arr[-1] % 1000000007


class Solution:

	def firstElement(self, n):
		dp = [1, 1]
		for i in range(2, n + 1):
			dp.append((dp[i - 1] + dp[i - 2]) % 1000000007)
		return dp[n - 1]


class Solution:

	def firstElement(self, n):
		a = 0
		b = 1
		m = 10 ** 9 + 7
		for r in range(1, n):
			c = b
			b = (b + a) % m
			a = c
		return b


class Solution:

	def firstElement(self, n):
		mod = 1000000000.0 + 7
		if n == 0:
			return 0
		elif n == 1:
			return 1
		else:
			dp = [0 for _ in range(n + 1)]
			dp[0] = 0
			dp[1] = 1
			for i in range(2, n + 1):
				dp[i] = (dp[i - 1] % mod + dp[i - 2] % mod) % mod
			return int(dp[n] % mod)


class Solution:

	def firstElement(self, n):
		a = 1
		b = 1
		if n == 1 or n == 2:
			return 1
		else:
			for i in range(2, n):
				c = a + b
				if a <= b:
					a = c
				else:
					b = c
			if c >= 1000000007:
				return c % 1000000007
			else:
				return c


import numpy as np
N_MOD = 1000000007
_MAT = np.array([[1, 1], [1, 0]])

class Solution:

	def firstElement(self, n):
		prev = 0
		cur = 1
		for i in range(n - 1):
			tmp = cur + prev
			prev = cur
			cur = tmp
		return cur % N_MOD


class Solution:

	def firstElement(self, n):
		if n == 1 or n == 2:
			return 1
		mod = 1000000000.0 + 7
		a = 1
		b = 1
		c = a + b
		for i in range(1, n - 1):
			c = (a + b) % mod
			a = b
			b = c
		return int(c)


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

def power(a, n):
	md = 10 ** 9 + 7
	b = [[1, 1], [1, 0]]
	if n == 1:
		return a[1][0]
	power(a, int(n / 2))
	a = mult(a, a)
	if n % 2 != 0:
		a = mult(a, b)
	return a[1][0] % md

class Solution:

	def firstElement(self, n):
		a = [[1, 1], [1, 0]]
		return power(a, n)


import numpy as np

class Solution:

	def firstElement(self, n):
		prev2 = 0
		prev = 1
		for i in range(2, n + 1):
			curr = (prev2 + prev) % 1000000007
			prev2 = prev
			prev = curr
		return prev


class Solution:

	def firstElement(self, n):
		x = 1
		y = 1
		z = 1
		while z < n:
			c = x + y
			y = x
			x = c
			z += 1
		return y % 1000000007


class Solution:

	def multipleMatrix(self, a):
		a[0][0] = a[0][0] + a[0][1]
		a[0][1] = a[1][0]
		a[1][0] = a[0][0]
		a[1][1] = a[0][1]

	def firstElement(self, n):
		a = [[1 for x in range(2)] for y in range(2)]
		a[1][1] = 0
		for i in range(n - 2):
			self.multipleMatrix(a)
		return a[1][0] % 1000000007


import math

class Solution:

	def firstElement(self, n):
		if n == 1:
			return 1
		m = [[1, 1], [1, 0]]
		prod = [[1, 0], [0, 1]]
		for i in range(n):
			prod = [[(prod[0][0] * m[0][0] + prod[0][1] * m[1][0]) % 1000000007, (prod[0][0] * m[0][1] + prod[0][1] * m[1][1]) % 1000000007], [(prod[1][0] * m[0][0] + prod[1][1] * m[1][0]) % 1000000007, (prod[1][0] * m[0][1] + prod[1][1] * m[1][1]) % 1000000007]]
		return prod[1][0]


class Solution:

	def firstElement(self, n):
		f = 1
		s = 1
		t = f + s
		if n == 1:
			return f
		if n == 2:
			return s
		if n == 3:
			return t
		for i in range(4, n + 1):
			f = s
			s = t
			t = (f + s) % 1000000007
		return t


class Solution:

	def multiply(self, m1, m2):
		a00 = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]
		a01 = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]
		a10 = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]
		a11 = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]
		return [[a00, a01], [a10, a11]]

	def recurse(self, n, matrix, solved):
		if solved[n] == True:
			return matrix[n]
		m1 = self.recurse(n // 2, matrix, solved)
		m1 = self.multiply(m1, m1)
		if n % 2 == 0:
			return m1
		else:
			return self.multiply(m1, matrix[1])

	def firstElement(self, n):
		matrix = [[[1, 1], [1, 0]] for i in range(n + 1)]
		solved = [False] * (n + 1)
		solved[1] = True
		return self.recurse(n, matrix, solved)[1][0] % 1000000007


class Solution:

	def firstElement(self, n):
		a00 = 1
		a01 = 1
		a10 = 1
		a11 = 0
		i = 2
		if n == 1:
			return a10
		else:
			while i <= n:
				a = a00 * 1 + a01 * 1
				b = a00 * 1 + a01 * 0
				c = a10 * 1 + a11 * 1
				d = a10 * 1 + a11 * 0
				a00 = a
				a01 = b
				a10 = c
				a11 = d
				i += 1
			return a10 % 1000000007