A Lucas Number is a number which is represented by the following recurrence
L_{n} = L_{n-1} + L_{n-2} for n>1
L_{0} = 2
L_{1} = 1
Given a number N, find the N^{th} lucas number.
Note: Since the output may be very large calculate the answer modulus 10^9+7.
Example 1:
Input:
N = 5
Output: 11
Explanation: L_{3} + L_{4} = L5
L_{3 }= 4 and L_{4} = 7
Ã¢â¬â¹Example 2:
Input: 
N = 7
Output: 29
Explanation: L_{5} + L_{6} = L_{7}
L_{5}_{ }= 11 and L_{6} = 18
Your Task:
You don't need to read input or print anything. Your task is to complete the function lucas() which takes integer N  as input parameter and return N^{th}  Lucas number.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{6}

Difficulty: EASY
Tags: Dynamic programming

Mathematics
Skill types: Dynamic programming
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def lucas(self, n):

        # code here 

Solutions:
class Solution:

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


class Solution:

	def lucas(self, n):
		if n == 0:
			return 2
		elif n == 1:
			return 1
		else:
			(a, b) = (2, 1)
			for i in range(n - 1):
				c = a + b
				a = b
				b = c
			return c % (int(1000000000.0) + 7)


class Solution:

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


class Solution:

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


class Solution:

	def lucas(self, n):
		if n == 0:
			return 2
		if n == 1:
			return 1
		mod = 10 ** 9 + 7
		a = 2
		b = 1
		c = -1
		for i in range(2, n + 1):
			c = (a + b) % mod
			a = b % mod
			b = c
		return c


class Solution:

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


class Solution:

	def lucas(self, n):
		(l0, l1) = (2, 1)
		for i in range(2, n + 1):
			(l0, l1) = (l1, l0 + l1)
		return l1 % 1000000007


class Solution:
	from typing import Iterator

	def lucas(self, n: int) -> int:
		gen = self.generator()
		for _ in range(n):
			next(gen)
		return next(gen) % 1000000007

	def generator(self) -> Iterator[int]:
		(a, b) = (2, 1)
		while True:
			yield a
			(a, b) = (b, a + b)


class Solution:

	def lucas(self, n):
		a = 2
		b = 1
		m = 10 ** 9 + 7
		for i in range(2, n + 2):
			(a, b) = (b, a + b)
			a = a % m
			b = b % m
		return a
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.lucas(n))


class Solution:

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


class Solution:

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


class Solution:

	def lucas(self, n):
		if n <= 1:
			return 2 - n
		first = 2
		second = 1
		output = 0
		mod = 10 ** 9 + 7
		for i in range(2, n + 1):
			output = (first + second) % mod
			first = second
			second = output
		return output


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def lucas(self, n):
		luc = [2, 1]
		for j in range(2, n + 1):
			luc.append((luc[-1] + luc[-2]) % (10 ** 9 + 7))
		return luc[-1]


class Solution:

	def lucas(self, n):
		a = 2
		b = 1
		for i in range(n - 1):
			(b, a) = (a + b, b)
		return b % (10 ** 9 + 7)


class Solution:

	def lucas(self, n):
		dp = [2, 1]
		for i in range(2, n + 1):
			x = dp[1]
			new = dp[0] + dp[1]
			dp[0] = dp[1]
			dp[1] = new
		return dp[1] % 1000000007


class Solution:

	def lucas(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 3
		a = 2
		b = 1
		for e in range(n - 1):
			c = a + b
			a = b
			b = c
		return c % (10 ** 9 + 7)


class Solution:

	def lucas(self, n):
		mod = 10 ** 9 + 7
		l = [2, 1]
		if n <= 1:
			return l[n]
		p2 = 2
		p1 = 1
		k = 2
		cur = p1 + p2
		while k < n:
			nex = cur + p1
			p2 = p1
			p1 = cur
			cur = nex
			k += 1
		return cur % mod