Given a positive integer N, find the Nth Even Fibonacci number. Since the answer can be very large, return the answer modulo 1000000007.
Example 1:
Input: n = 1
Output: 2 
Explanation: 2 is the first even
number in the fibonacci series.
Example 2:
Input: n = 2
Output: 8
Explanation: 8 is the second even
number in the fibonacci series.
Your Task:  
You dont need to read input or print anything. Complete the function nthEvenFibonacci() which takes S as input parameter and returns the Nth even fibonacci number.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1<= n <=1000

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

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

Solutions:
class Solution:

	def nthEvenFibonacci(ob, n):
		a = 1
		b = 1
		z = 0
		c = 0
		while c != n:
			z = a + b
			a = b
			b = z
			if z % 2 == 0:
				c += 1
		return z % 1000000007


class Solution:

	def nthEvenFibonacci(self, n):
		net = n * 3
		return self.gfn(net) % 1000000007

	def gfn(self, n):
		if n < 1:
			return 0
		n1 = 0
		n2 = 1
		while n > 1:
			n2 += n1
			n1 = n2 - n1
			n -= 1
		return n2


class Solution:

	def nthEvenFibonacci(ob, n):
		dp = [0] * (3 * n)
		dp[0] = 1
		dp[1] = 1
		i = 2
		f = 0
		while f < n:
			dp[i] = dp[i - 1] + dp[i - 2]
			if dp[i] % 2 == 0:
				f += 1
				if f == n:
					return dp[i] % 1000000007
			i += 1


class Solution:

	def nthEvenFibonacci(ob, n):
		ob.n = n
		ob.l = [0, 1]
		ob.a = 0
		ob.b = 1
		for i in range(1, 3 * n):
			ob.c = ob.a + ob.b
			ob.l.append(ob.c)
			(ob.a, ob.b) = (ob.b, ob.c)
		return ob.l[-1] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		a = 0
		b = 1
		l = []
		while 1:
			c = a + b
			if a % 2 == 0:
				l.append(a)
			a = b
			b = c
			if len(l) == n + 1:
				break
		return l[-1] % (10 ** 9 + 7)


class Solution:

	def nthEvenFibonacci(ob, n):
		(f1, f2) = (0, 1)
		f = []
		c = 0
		while c != n:
			f3 = f1 + f2
			if f3 % 2 == 0:
				f.append(f3 % (10 ** 9 + 7))
				c += 1
			f1 = f2
			f2 = f3
		return f[n - 1]


class Solution:

	def nthEvenFibonacci(ob, n):
		even_counter = 0
		prev_fib = 1
		cur_fib = 1
		while even_counter < n:
			next_fib = prev_fib + cur_fib
			if next_fib % 2 == 0:
				even_counter += 1
			prev_fib = cur_fib
			cur_fib = next_fib
		return next_fib % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		fibos = []
		fibos.append(0)
		fibos.append(1)
		evens = 0
		i = 2
		while evens < n:
			fibos.append(fibos[i - 1] + fibos[i - 2])
			if fibos[i] % 2 == 0:
				evens = evens + 1
			if evens == n:
				return fibos[i] % (pow(10, 9) + 7)
			i = i + 1
		return -1


class Solution:

	def nthEvenFibonacci(ob, N):
		i = 0
		j = 0
		k = 0
		l = 0
		f1 = 0
		f2 = 1
		f3 = 0
		while l < N:
			f3 = f1 + f2
			f1 = f2
			f2 = f3
			if f3 % 2 == 0:
				l = l + 1
			f3 = f3 % 1000000007
		return f3 % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		a = 0
		b = 1
		lst = []
		for i in range(0, n * 2):
			a = b + a
			b = b + a
			if a % 2 == 0:
				lst.append(a)
			if b % 2 == 0:
				lst.append(b)
			if len(lst) == n + 1:
				break
		return lst[n - 1] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		n1 = 1
		n2 = 1
		k = 1
		while k <= n:
			if n2 % 2 == 0:
				k += 1
			(n1, n2) = (n2, n1 + n2)
		return n1 % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		mod = 1000000007
		(a, b, c) = (0, 1, 1)
		i = 1
		while i < 3 * n:
			c = (a + b) % mod
			a = b
			b = c
			i += 1
		return c % mod


class Solution:

	def nthEvenFibonacci(ob, n):
		(a, b) = (1, 1)
		m = 10 ** 9 + 7
		for i in range(3 * n - 2):
			c = (a + b) % m
			a = b
			b = c
		return b


class Solution:

	def nthEvenFibonacci(ob, N):
		first = 0
		second = 1
		third = 1
		count = 0
		while True:
			third = first + second
			first = second
			second = third
			if third % 2 == 0:
				count = count + 1
			if count == N:
				return third % 1000000007


class Solution:

	def nthEvenFibonacci(self, n):
		a = 0
		b = 1
		even_count = 0
		if n <= 0:
			return 'Incorrect Input'
		else:
			for i in range(2, 10000):
				c = a + b
				a = b
				b = c
				if c % 2 == 0:
					even_count += 1
				if even_count == n:
					return c % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		x = 0
		y = 1
		sum = 0
		count = 0
		while count != n:
			sum = x + y
			x = y
			y = sum
			if sum % 2 == 0:
				count = count + 1
		return sum % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		if n <= 1:
			return n
		elif n == 1:
			return 2
		else:
			a = 0
			b = 1
			c = 0
			for i in range(1, n * 3):
				c = a + b
				a = b
				b = c
			return c % (10 ** 9 + 7)


class Solution:

	def nthEvenFibonacci(ob, n):
		k = 0
		y = [0, 1]
		while k != n:
			y.append(y[-1] + y[-2])
			if y[-1] % 2 == 0:
				k += 1
		return y[-1] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		count = 0
		a = 1
		b = 1
		while count < n:
			num = a + b
			a = b
			b = num
			if num % 2 == 0:
				count += 1
			if count == n:
				return num % 1000000007
				break


class Solution:

	def nthEvenFibonacci(ob, n):
		(a, b) = (1, 1)
		while n:
			(a, b) = (b, a + b)
			if a % 2 == 0:
				n -= 1
		return a % int(1000000000.0 + 7)


class Solution:

	def nthEvenFibonacci(ob, n):
		index = n * 3
		l = [0, 1]
		for i in range(2, index + 1):
			l.append(l[i - 2] + l[i - 1])
		return l[index] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		c = 0
		x = 1
		y = 1
		while c < n:
			(x, y) = (y, x + y)
			if y % 2 == 0:
				c += 1
		return y % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		count = 0
		a = 1
		b = 1
		while count != n:
			t = a
			a = b
			b = t + b
			if b % 2 == 0:
				count += 1
		return b % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		a = 0
		b = 1
		while n > 0:
			value = a
			a = b
			b = value + b
			if b % 2 == 0:
				n = n - 1
		m = 1000000007
		return b % m


class Solution:

	def nthEvenFibonacci(ob, n):
		fib = [1, 1]
		x = 2
		while n > 0:
			fib += [fib[-1] + fib[-2]]
			if fib[-1] % 2 == 0:
				x = fib[-1]
			else:
				continue
			n -= 1
		return x % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		(x, y, z, k) = (0, 1, 1, 0)
		while k != n:
			if z % 2 == 0:
				k += 1
				if k == n:
					return z % (10 ** 9 + 7)
			x = y
			y = z
			z = x + y


class Solution:

	def nthEvenFibonacci(ob, n):
		p = 1000000007
		fib = [1 for _ in range(3 * n + 1)]
		for i in range(3, 3 * n + 1):
			fib[i] = (fib[i - 1] % p + fib[i - 2] % p) % p
		return fib[3 * n]


class Solution:

	def nthEvenFibonacci(ob, n):
		even = 0
		fib = [1, 1]
		while even != n:
			fib.append(fib[-1] + fib[-2])
			if fib[-1] % 2 == 0:
				even += 1
		return fib[-1] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		count = 0
		x = 0
		y = 1
		mod = 10 ** 9 + 7
		while True:
			c = x + y
			x = y
			y = c
			if y % 2 == 0:
				count += 1
			if count == n:
				break
		return y % mod


class Solution:

	def nthEvenFibonacci(ob, N):
		(a, b, c) = (0, 1, 1)
		while N > 0:
			c = a + b
			(a, b) = (b, c)
			if c % 2 == 0:
				N -= 1
		return c % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		a = [0] * (3 * n + 1)
		for i in range(1, 3 * n + 1):
			if i == 1:
				a[i] = 1
			else:
				a[i] = a[i - 1] + a[i - 2]
		return a[3 * n] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		n = 3 * n
		dp = [0] * (n + 1)
		mod = 1000000007
		dp[0] = 0
		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 nthEvenFibonacci(ob, n):
		m = 10 ** 9 + 7
		(a, b, c, z) = (1, 1, 0, 0)
		while c != n:
			z = a + b
			a = b
			b = z
			if z % 2 == 0:
				c += 1
		return z % m


class Solution:

	def nthEvenFibonacci(ob, n):
		x = [0, 1]
		count = 0
		for i in range(10000):
			a = x[-1] + x[-2]
			if a % 2 == 0:
				count += 1
			if count == n:
				return a % 1000000007
			else:
				x.append(a)


class Solution:

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


class Solution:

	def nthEvenFibonacci(ob, n):
		(a, b) = (0, 1)
		c = 0
		d = 0
		for i in range(0, 9999999):
			c = a + b
			a = b
			b = c
			if c % 2 == 0:
				d += 1
				if d == n:
					return c % 1000000007
					break


class Solution:

	def nthEvenFibonacci(ob, n):
		a = 0
		b = 1
		arr = []
		while len(arr) != n:
			res = a + b
			if res % 2 == 0:
				arr.append(res)
			a = b
			b = res
		return arr[n - 1] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		M = 10 ** 9 + 7
		cnt = 0
		(a, b) = (1, 1)
		f = 0
		while cnt != n:
			f = a + b
			a = b
			b = f
			if f & 1 == 0:
				cnt += 1
		return f % M


class Solution:

	def nthEvenFibonacci(ob, n):
		a = 2
		b = 8
		c = 1
		if n == 1:
			return a
		if n == 2:
			return b
		for i in range(3, n + 1):
			c = (4 * b + a) % 1000000007
			a = b
			b = c
		return c


class Solution:

	def nthEvenFibonacci(ob, n):
		h = 2
		s = 8
		if n == 1:
			return h
		if n == 2:
			return s
		for i in range(3, n + 1):
			q = (4 * s + h) % 1000000007
			(h, s) = (s, q)
		return q % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		even = []
		fib = [1, 1]
		while len(even) < n:
			t = fib[-1] + fib[-2]
			if t % 2 == 0:
				even.append(t)
			fib.append(t)
		return even[n - 1] % (10 ** 9 + 7)


class Solution:

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


class Solution:

	def nthEvenFibonacci(ob, n):
		a = 1
		b = 1
		for i in range(1, 3 * n - 1):
			s = a + b
			a = b
			b = s
		return s % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		list1 = [0, 1, 1]
		i = 0
		count = 0
		while i <= 3 * n:
			n3 = list1[-1] + list1[-2]
			if n3 % 2 == 0:
				count += 1
			list1.append(n3)
			if count == n:
				return n3 % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthEvenFibonacci(n))


class Solution:

	def nthEvenFibonacci(ob, n):
		count = 0
		a1 = 0
		a2 = 1
		while count < n:
			temp = a2
			a2 = a1 + a2
			a1 = temp
			if a2 % 2 == 0:
				count += 1
		return a2 % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthEvenFibonacci(n))


class Solution:
	fs = [1, 1]
	while len(fs) < 3000:
		fs.append(fs[-1] + fs[-2])

	def nthEvenFibonacci(ob, n):
		return ob.fs[n * 3 - 1] % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthEvenFibonacci(n))


class Solution:

	def nthEvenFibonacci(ob, n):
		a = 1
		b = 1
		z = 0
		count = 0
		while count != n:
			z = a + b
			a = b
			b = z
			if z % 2 == 0:
				count += 1
		return z % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthEvenFibonacci(n))


class Solution:

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


class Solution:

	def nthEvenFibonacci(ob, n):
		(a, b, c) = (1, 1, 0)
		c1 = 0
		while c1 != n:
			c = a + b
			(a, b) = (b, c)
			if ~c & 1:
				c1 += 1
		return c % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		a0 = 0
		a1 = 1
		num = 0
		count = 0
		while count != n:
			num = a0 + a1
			a0 = a1
			a1 = num
			if num % 2 == 0:
				count += 1
		return num % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		c = [1, 1]
		i = 0
		a = 0
		while True:
			c.append(c[i] + c[i + 1])
			i += 1
			if c[-1] % 2 == 0:
				a += 1
				if a == n:
					return c[-1] % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		if n == 0:
			return 0
		x = [0, 1, 1]
		while n > 0:
			x[0] = int(x[1] + x[2])
			(x[0], x[1]) = (x[1], x[0])
			(x[1], x[2]) = (x[2], x[1])
			if x[2] % 2 == 0:
				n -= 1
		return int(x[2] % 1000000007)


class Solution:

	def nthEvenFibonacci(ob, n):
		t1 = 1
		t2 = 1
		s = 0
		c = 0
		while c != n:
			s = t1 + t2
			t1 = t2
			t2 = s
			if s % 2 == 0:
				c = c + 1
		return s % 1000000007


class Solution:

	def nthEvenFibonacci(ob, n):
		f = 0
		s = 1
		flag = False
		c = 0
		while flag == False:
			digit = f + s
			if digit % 2 == 0:
				c = c + 1
				if c == n:
					flag = True
					return digit % 1000000007
				else:
					f = s
					s = digit
			else:
				f = s
				s = digit