Given a floor of dimensions 2 x W and tiles of dimensions 2 x 1, the task is to find the number of ways the floor can be tiled. A tile can either be placed horizontally i.e as a 1 x 2 tile or vertically i.e as 2 x 1 tile. Print the answer modulo 10^{9}+7.
 
Example 1:
Input:
W = 3
Output:
3
Explanation:
We need 3 tiles to tile the board
of size  2 x 3. 
We can tile in following ways:
1) Place all 3 tiles vertically. 
2) Place first tile vertically.
and remaining 2 tiles horizontally.
3) Place first 2 tiles horizontally
and remaining tiles vertically.
Example 2:
Input:
W = 4
Output:
5
Explanation:
For a 2 x 4 board, there are 5 ways
1) All 4 vertical
2) All 4 horizontal
3) First 2 vertical, remaining
2 horizontal.
4) First 2 horizontal, remaining
2 vertical.
5) Corner 2 vertical, middle
2 horizontal.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function numberOfWays() which takes an Integer N as input and returns the answer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def numberOfWays(self, N):
        # code here

Solutions:
class Solution:

	def numberOfWays(self, N):
		if N <= 2:
			return N
		a = 1
		b = 2
		for i in range(3, N + 1):
			res = (a + b) % (10 ** 9 + 7)
			a = b
			b = res
		return res


class Solution:

	def numberOfWays(self, N):
		if N == 1:
			return 1
		elif N == 2:
			return 2
		fs = 1
		ss = 2
		for i in range(3, N + 1):
			res = fs + ss
			fs = ss
			ss = res
		return res % 1000000007


class Solution:

	def numberOfWays(self, n):
		(a, b) = (1, 2)
		mod = 10 ** 9 + 7
		if n <= 2:
			return n
		for i in range(3, n + 1):
			(a, b) = (b, (a + b) % mod)
		return b


from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

class Solution:

	def numberOfWays(self, N):
		MOD = 10 ** 9 + 7
		dp = [1, 1]
		for i in range(2, N + 1):
			dp.append((dp[i - 1] + dp[i - 2]) % MOD)
		return dp[N]


class Solution:

	def numberOfWays(self, n):
		a = 1
		mod = 1000000000.0 + 7
		b = 1
		e = 2
		while e <= n:
			c = (a + b) % mod
			a = b
			b = c
			e += 1
		return int(b)


class Solution:

	def numberOfWays(self, N):
		if N == 1:
			return 1
		f = 1
		s = 1
		m = 10 ** 9 + 7
		for i in range(2, N + 1):
			curr = (f % m + s % m) % m
			f = s
			s = curr
		return s


class Solution:

	def numberOfWays(self, N):
		(a, b) = (1, 2)
		if N == 1:
			return a
		if N == 2:
			return b
		s = 0
		while N > 2:
			s = a + b
			a = b
			b = s
			N = N - 1
		return b % (10 ** 9 + 7)


def numberOfWaysToTile(n):
	if n == 1:
		return 1
	elif n == 2:
		return 2
	a = 1
	b = 2
	while n > 2:
		(b, a) = ((b + a) % 1000000007, b % 1000000007)
		n -= 1
	return b

class Solution:

	def numberOfWays(self, N):
		return numberOfWaysToTile(N)


class Solution:

	def numberOfWays(self, N):
		mod = 10 ** 9 + 7
		dp = [0] * (N + 1)
		dp[0] = 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 numberOfWays(self, N):
		if N == 1:
			return 1
		elif N == 2:
			return 2
		else:
			first = 1
			second = 2
			ans = first + second
			while N - 3:
				first = second
				second = ans
				ans = first + second
				N -= 1
		return ans % 1000000007


class Solution:

	def numberOfWays(self, N):
		dp = [1] * (N + 1)
		for i in range(N + 1):
			if i <= 2:
				dp[i] = i
			else:
				dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)
		return dp[N]


class Solution:

	def numberOfWays(self, N):
		fn = 1
		fn2 = 2
		res = 0
		if N == 1:
			return 1
		if N == 2:
			return 2
		for i in range(3, N + 1):
			res = (fn2 + fn) % int(1000000000.0 + 7)
			fn = fn2
			fn2 = res
		return res


class Solution:

	def numberOfWays(self, N):
		dp = [1 for _ in range(N + 1)]
		for i in range(0, N + 1):
			if i <= 2:
				dp[i] = i
			else:
				dp[i] = (dp[i - 1] + dp[i - 2]) % (1000000000.0 + 7)
		return int(dp[N])


class Solution:

	def numberOfWays(self, N):
		(a, b) = (0, 1)
		for i in range(N):
			s = a + b
			a = b % (10 ** 9 + 7)
			b = s % (10 ** 9 + 7)
		return b


class Solution:

	def numberOfWays(self, N):
		a = 1
		b = 1
		for i in range(2, N + 1):
			c = (a + b) % (10 ** 9 + 7)
			(a, b) = (b, c)
		return b


class Solution:

	def numberOfWays(self, N):
		if N == 1 or N == 2:
			return N
		dp = [0 for i in range(N + 1)]
		dp[1] = 1
		dp[2] = 2
		for i in range(3, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def numberOfWays(self, N):
		(f1, f2) = (0, 1)
		f = [0, 1]
		for i in range(N):
			f3 = (f1 + f2) % (10 ** 9 + 7)
			f.append(f3)
			f1 = f2
			f2 = f3
		return f[N + 1]


class Solution:

	def numberOfWays(self, N):
		if N == 1:
			return 1
		if N == 2:
			return 2
		MOD = 1000000000 + 7
		dp = [0] * (N + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
		return dp[-1]


class Solution:

	def numberOfWays(self, N):
		fib = [0] * 10 ** 5
		fib[1] = 1
		fib[2] = 2
		for i in range(3, N + 1):
			fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000007
		return fib[N]


class Solution:

	def numberOfWays(self, N):
		if N <= 3:
			return N
		mod = 1000000007
		prev = 3
		prevprev = 2
		for i in range(4, N + 1):
			present = (prev % mod + prevprev % mod) % mod
			prevprev = prev
			prev = present
		return present % mod


class Solution:

	def numberOfWays(self, N):
		ans = (N + 1) * [0]
		for i in range(1, N + 1):
			if i <= 2:
				ans[i] = i
			else:
				ans[i] = (ans[i - 1] + ans[i - 2]) % 1000000007
		return ans[N]


class Solution:

	def numberOfWays(self, n):
		MOD = 10 ** 9 + 7
		if n <= 2:
			return n
		prevPrev = 1
		prev = 2
		res = 0
		for i in range(3, n + 1):
			res = (prev + prevPrev) % MOD
			prevPrev = prev
			prev = res
		return res


MOD = int(1000000000.0 + 7)

class Solution:

	def numberOfWays(self, n: int):
		if n <= 2:
			return n
		prevPrev = 1
		prev = 2
		res = 0
		for i in range(3, n + 1):
			res = (prev + prevPrev) % MOD
			prevPrev = prev
			prev = res
		return res


class Solution:

	def numberOfWays(self, N):
		(a, b, c, N) = (1, 1, 2, N + 1)
		if N == 2:
			return b
		while c < N:
			(a, b, c) = (b, a + b, c + 1)
			if c == N:
				return b % 1000000007


import sys
sys.setrecursionlimit(1000000)

class Solution:
	cache = dict()

	def numberOfWays(self, n):
		if n < 2:
			return 1
		if self.cache.get(n):
			return self.cache.get(n)
		value = self.numberOfWays(n - 1) + self.numberOfWays(n - 2)
		self.cache[n] = value % 1000000007
		return value % 1000000007


class Solution:

	def numberOfWays(self, n):
		if n in [1, 2]:
			return n
		f = 1
		s = 2
		for i in range(3, n + 1):
			(f, s) = (s, f + s)
		return s % (pow(10, 9) + 7)


class Solution:

	def numberOfWays(self, N):
		if N == 1:
			return 1
		first = 0
		second = 0
		if N > 1:
			first = 1
			second = 2
			current = 2
			for i in range(3, N + 1):
				current = first + second
				first = second
				second = current
		return current % 1000000007


class Solution:

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


class Solution:

	def numberOfWays(self, N):
		mod = int(1000000000.0 + 7)
		dp = [1] * (N + 1)
		for i in range(2, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod
		return dp[N]


class Solution:

	def numberOfWays(self, N):
		perms = [1, 1]
		for num in range(2, N + 1):
			perms.append((perms[num - 1] + perms[num - 2]) % 1000000007)
		return perms[N]


class Solution:

	def numberOfWays(self, N):
		a = 1
		b = 2
		if N == 1:
			return a
			exit
		else:
			for j in range(3, N + 1):
				value = a
				a = b
				b = value + b
		m = 1000000007
		return b % m


class Solution:

	def numberOfWays(self, N):
		if N < 3:
			return N
		(n1, n2) = (1, 2)
		for i in range(3, N + 1):
			(n2, n1) = (n2 + n1, n2)
		mod = 10 ** 9 + 7
		return n2 % mod


P = 10 ** 9 + 7

class Solution:

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


class Solution:

	def numberOfWays(self, N):
		f0 = 1
		f1 = 1
		for j in range(N - 1):
			f2 = f1 + f0
			f0 = f1
			f1 = f2
		return f1 % 1000000007


class Solution:

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


class Solution:

	def numberOfWays(self, N):
		(a, b) = (0, 1)
		for _ in range(N):
			(a, b) = (b, a + b)
		return b % 1000000007


import math
dp = [x for x in range(100007)]
prime = int(math.pow(10, 9)) + 7
for i in range(3, len(dp)):
	dp[i] = dp[i - 1] % prime + dp[i - 2] % prime
	dp[i] = dp[i] % prime

class Solution:

	def numberOfWays(self, N):
		return dp[N]


class Solution:

	def numberOfWays(self, N):
		if N == 1 or N == 2:
			return N
		a = 1
		b = 2
		for i in range(N - 2):
			c = (a + b) % 1000000007
			a = b
			b = c
		return b


class Solution:

	def numberOfWays(self, N):
		if N == 1 or N == 2:
			return N
		ans = [1, 2]
		for i in range(N - 2):
			ans.append((ans[-2] + ans[-1]) % 1000000007)
		return ans[-1]


import math

class Solution:

	def numberOfWays(self, N):
		if N < 3:
			return N
		(f, s) = (1, 2)
		mod = pow(10, 9) + 7
		for i in range(3, N + 1):
			curr = f + s
			curr = curr % mod
			f = s
			s = curr
		return s


class Solution:
	modulo = 10 ** 9 + 7

	def numberOfWays(self, n):
		f = 1
		s = 1
		for i in range(2, n + 1):
			(s, f) = (f + s, s)
		return s % self.modulo


class Solution:

	def numberOfWays(self, N):
		n1 = 1
		n2 = 1
		fib = 1
		for i in range(2, N + 1):
			fib = n1 + n2
			n1 = n2
			n2 = fib
		return fib % (10 ** 9 + 7)


class Solution:

	def numberOfWays(self, N):
		(a, b, c) = (0, 1, 1)
		while N > 0:
			c = a + b
			(a, b) = (b, c)
			N -= 1
		return c % 1000000007


MOD = 1000000000.0 + 7

class Solution:

	def numberOfWays(self, n):
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
		return int(dp[n])


mod = 1000000000.0 + 7

class Solution:

	def numberOfWays(self, N):
		if N <= 2:
			return N
		diff1 = 2
		diff2 = 1
		ans = 2
		for i in range(2, N):
			ans = int((diff1 + diff2) % mod)
			(diff1, diff2) = (ans, diff1)
		return ans


class Solution:

	def numberOfWays(self, N):
		if N > 32509:
			print(N)
			return -1
		fib = [0] * 100005
		fib[1] = 1
		fib[2] = 2
		for i in range(3, N + 1):
			fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000007
		return fib[N]


class Solution:

	def numberOfWays(self, n):
		a = b = 1
		for i in range(1, n):
			t = a + b
			a = b
			b = t
		return b % 1000000007


class Solution:

	def numberOfWays(self, N):
		if N < 2:
			return N
		prev_0 = 1
		prev_1 = 1
		mod = 10 ** 9 + 7
		for i in range(2, N + 1):
			(prev_1, prev_0) = ((prev_0 % mod + prev_1 % mod) % mod, prev_1)
		return prev_1


class Solution:

	def numberOfWays(self, N):
		if N <= 3:
			return N
		prev = 1
		pres = 1
		for i in range(2, N + 1, 1):
			temp = prev
			prev = pres
			pres = temp + pres
		return pres % (10 ** 9 + 7)


class Solution:

	def numberOfWays(self, N):
		F = [0 for i in range(N + 1)]
		if N < 3:
			return N
		F[0] = 1
		F[1] = 1
		mod = int(1000000000.0 + 7)
		for i in range(2, N + 1):
			F[i] = (F[i - 1] + F[i - 2]) % mod
		return F[N]


class Solution:

	def numberOfWays(self, N):
		mod = 1000000007
		a = 1
		b = 2
		if a == N:
			return N
		elif b == N:
			return N
		i = 2
		while i <= N:
			c = a + b
			a = b
			b = c
			i += 1
		return a % mod


class Solution:

	def numberOfWays(self, N):
		a = 1
		b = 2
		if N == 1:
			return a
		else:
			for i in range(N - 2):
				temp = b + a
				a = b
				b = temp
			return b % 1000000007


class Solution:

	def numberOfWays(self, N):
		m = 10 ** 9 + 7
		d = {0: 1, 1: 1}
		for i in range(2, N + 1):
			d[i] = d[i - 1] % m + d[i - 2] % m
		return d[N] % m


class Solution:

	def numberOfWays(self, N):
		if N <= 2:
			return N
		a = 1
		b = 2
		r = 0
		for i in range(3, N + 1):
			r = (b + a) % int(1000000000.0 + 7)
			a = b
			b = r
		return r


class Solution:

	def numberOfWays(self, N):
		if N <= 2:
			return N
		prev2prev = 1
		prev = 2
		res = 0
		for i in range(3, N + 1):
			res = (prev + prev2prev) % (10 ** 9 + 7)
			prev2prev = prev
			prev = res
		return res


class Solution:

	def numberOfWays(self, N):
		if N == 1 or N == 0 or N == 2:
			return N
		ans = 0
		a = 1
		b = 2
		for i in range(3, N + 1):
			ans = (a + b) % (10 ** 9 + 7)
			a = b
			b = ans
		return ans


class Solution:

	def numberOfWays(self, N, cache={}):

		def fiblog(N, cache):
			if N == 0 or N == 1:
				return 1
			if N == 2:
				return 2
			if N in cache:
				return cache[N]
			idx = N // 2
			if N % 2 == 0:
				n1 = fiblog(idx, cache)
				n2 = fiblog(idx - 1, cache)
				cache[idx] = n1
				cache[idx - 1] = n2
				return n1 * n1 + n2 * n2
			else:
				n1 = fiblog(idx + 1, cache)
				n2 = fiblog(idx - 1, cache)
				cache[idx + 1] = n1
				cache[idx - 1] = n2
				return n1 * n1 - n2 * n2
		ans = fiblog(N, {})
		return ans % (10 ** 9 + 7)


class Solution:

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


class Solution:
	dp = [0] * (100000 + 1)
	dp[1] = 1
	dp[0] = 1
	n = 1

	def numberOfWays(self, N):
		if N <= self.n:
			return self.dp[N]
		for i in range(self.n + 1, N + 1):
			self.dp[i] = self.dp[i - 1] + self.dp[i - 2]
		self.n = N
		return self.dp[N] % (1000000000 + 7)


class Solution:

	def numberOfWays(self, N):
		prev2 = 1
		prev = 2
		if N == 0:
			return 0
		if N == 1:
			return 1
		for i in range(3, N + 1):
			curi = prev + prev2
			prev2 = prev
			prev = curi
		return prev % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.numberOfWays(N))


class Solution:

	def numberOfWays(self, N):
		fib = [0] * 100005
		fib[1] = 1
		fib[2] = 2
		for i in range(3, N + 1):
			fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000007
		return fib[N]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.numberOfWays(N))


class Solution:

	def numberOfWays(self, N):
		m = 10 ** 9 + 7
		d = {0: 1, 1: 1}
		for i in range(2, N + 1):
			d[i] = (d[i - 1] + d[i - 2]) % m
		return d[N] % m
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.numberOfWays(N))