Given N, the number of plots on either sides of the road. Find the total ways to construct buildings in the plots such that there is a space between any 2 buildings. All plots on one side of the road are continuous.
Lets suppose * represents a plot, then for N=3, the plots can be represented as * * * | | * * *                               
Where | | represents the road.                                                                                                                                                                  
Note: As the answer can be very large, print it mod 1000000007
 
Example 1:
Input: N = 3
Output: 25
Explanation: 3 plots, which means possible
ways for one side are BSS, BSB, SSS, SBS,
SSB where B represents a building and S
represents an empty space Total possible 
ways are 25, because a way to place on one
side can correspond to any of 5 ways on other
side.
Example 2:
Input: N = 10
Output: 20736
Explanation: There are 20736 ways for N = 10.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function TotalWays() which takes N as input parameter and returns the total possible ways modulo 10^{9} + 7.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
 
Constraints:
1 <= N <= 100000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Starter code: #User function Template for python3



class Solution:

	def TotalWays(self, N):

		# Code here

Solutions:
class Solution:

	def TotalWays(self, N):
		a = [0, 1]
		for i in range(N + 3):
			a.append(a[i] + a[i + 1])
		return a[N + 2] * a[N + 2] % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 1:
			return 4
		if N == 2:
			return 9
		dp = [-1 for i in range(N + 1)]
		dp[1] = 2
		dp[2] = 3
		for i in range(3, N + 1):
			dp[i] = dp[i - 1] + dp[i - 2]
		return dp[N] * dp[N] % int(1000000000.0 + 7)


class Solution:

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


class Solution:

	def TotalWays(self, N):
		dp0 = 1
		dp1 = 1
		for i in range(2, N + 1):
			(dp0, dp1) = (dp1, dp0 + dp1)
		return (dp0 + dp1) ** 2 % 1000000007


class Solution:

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


class Solution:

	def TotalWays(self, N):
		countB = 1
		countS = 1
		for _ in range(2, N + 1):
			prev_countB = countB
			prev_countS = countS
			countS = prev_countB + prev_countS
			countB = prev_countS
		result = countS + countB
		return result * result % 1000000007


class Solution:

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


class Solution:

	def TotalWays(self, N):
		b = [0] * (N + 1)
		s = [0] * (N + 1)
		s[1] = 1
		b[1] = 1
		for i in range(2, N + 1):
			b[i] = s[i - 1]
			s[i] = b[i - 1] + s[i - 1]
		ans = b[N] + s[N]
		return ans * ans % 1000000007


class Solution:

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


class Solution:

	def TotalWays(self, N):
		end_b = [0] * (N + 1)
		end_s = [0] * (N + 1)
		end_b[1] = 1
		end_s[1] = 1
		for i in range(2, N + 1):
			end_b[i] = end_s[i - 1]
			end_s[i] = end_b[i - 1] + end_s[i - 1]
		total = end_b[N] + end_s[N]
		return total * total % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 1:
			return 4
		if N == 0:
			return 0
		b = [0] * (N + 1)
		s = [0] * (N + 1)
		b[0] = 0
		s[0] = 0
		b[1] = 1
		s[1] = 1
		for i in range(2, N + 1):
			b[i] = s[i - 1]
			s[i] = s[i - 1] + b[i - 1]
			a = b[i] + s[i]
		return a * a % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 1:
			return 4
		b = 1
		s = 1
		for i in range(2, N + 1):
			p_b = b
			p_s = s
			s = p_s + p_b
			b = p_s
		res = b + s
		return res * res % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 1:
			return 4
		cob = 1
		cos = 1
		for i in range(2, N + 1):
			pre_cob = cob
			pre_cos = cos
			cos = pre_cos + pre_cob
			cob = pre_cos
		res = cob + cos
		return res * res % 1000000007


class Solution:

	def TotalWays(self, N):
		B = 1
		S = 1
		for i in range(2, N + 1):
			prevB = B
			prevS = S
			S = B + prevS
			B = prevS
		res = S + B
		return res * res % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 1:
			return 4
		B = 1
		S = 1
		for i in range(2, N + 1):
			prev_B = B
			prev_S = S
			S = prev_B + prev_S
			B = prev_S
		result = S + B
		return result * result % 1000000007


class Solution:

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


class Solution:

	def TotalWays(self, N):
		if N == 0:
			return 4
		countB = 1
		countS = 1
		for i in range(2, N + 1):
			prev_countB = countB
			prev_countS = countS
			countS = prev_countB + prev_countS
			countB = prev_countS
		res = countS + countB
		return res * res % 1000000007


class Solution:

	def TotalWays(self, N):
		end_with_zero = [0] * (N + 1)
		end_with_one = [0] * (N + 1)
		end_with_zero[1] = 1
		end_with_one[1] = 1
		for i in range(2, N + 1):
			end_with_zero[i] = end_with_zero[i - 1] + end_with_one[i - 1]
			end_with_one[i] = end_with_zero[i - 1]
		x = end_with_zero[-1] + end_with_one[-1]
		return x * x % (10 ** 9 + 7)


class Solution:

	def TotalWays(self, N):
		if N == 0:
			return 0
		b = 1
		s = 1
		for i in range(2, N + 1):
			c = b + s
			b = s
			s = c
		r = b + s
		return r * r % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 1:
			return 4
		B = 1
		S = 1
		for i in range(2, N + 1):
			previous_countB = B
			previous_countS = S
			S = previous_countB + previous_countS
			B = previous_countS
		c = S + B
		c = c * c
		return c % 1000000007


class Solution:

	def TotalWays(self, N):
		b = 1
		space = 1
		for i in range(2, N + 1):
			temp = space
			space = space + b
			b = temp
			b = b % 1000000007
			space = space % 1000000007
		ans = b + space
		return ans * ans % 1000000007


class Solution:

	def TotalWays(self, N):
		dpB = [0] * (N + 1)
		dpS = [0] * (N + 1)
		dpB[1] = 1
		dpS[1] = 1
		for i in range(2, N + 1):
			dpS[i] = dpB[i - 1] + dpS[i - 1]
			dpB[i] = dpS[i - 1]
		s = dpB[-1] + dpS[-1]
		return s * s % (10 ** 9 + 7)


class Solution:

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


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def TotalWays(self, N):
		dp = [[0 for i in range(2)] for i in range(N + 1)]
		dp[1][0] = 1
		dp[1][1] = 1
		for j in range(2, len(dp)):
			dp[j][0] = dp[j - 1][1]
			dp[j][1] = dp[j - 1][0] + dp[j - 1][1]
		return (dp[-1][0] + dp[-1][1]) ** 2 % (10 ** 9 + 7)


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def TotalWays(self, N):
		g = {}

		def recr(val, index):
			if (val, index) in g:
				return g[val, index]
			if index == N:
				return 1
			if val == '':
				ans = recr(0, index + 1) + recr(1, index + 1)
			elif val == 0:
				ans = recr(1, index + 1) + recr(0, index + 1)
			elif val == 1:
				ans = recr(0, index + 1)
			g[val, index] = ans
			return ans
		ans = recr('', 0) % (10 ** 9 + 7)
		ans = ans * ans % (10 ** 9 + 7)
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def TotalWays(self, N):
		building = [-1 for i in range(N)]
		space = [-1 for i in range(N)]
		building[0] = 1
		space[0] = 1
		MOD = 1000000007
		for i in range(1, N):
			building[i] = space[i - 1]
			space[i] = (building[i - 1] + space[i - 1]) % MOD
		cur = (building[N - 1] + space[N - 1]) % MOD
		return pow(cur, 2, MOD)


class Solution:

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


class Solution:

	def TotalWays(self, N):
		l = 10 ** 9 + 7
		if N == 1:
			return 4
		countB = 1
		countS = 1
		for i in range(2, N + 1):
			prev_countB = countB
			prev_countS = countS
			countS = prev_countB + prev_countS
			countB = prev_countS
		result = countS + countB
		return result * result % l


class Solution:

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


class Solution:

	def TotalWays(self, N):
		s = []
		s.append(1)
		s.append(2)
		for i in range(N):
			s.append(s[-1] + s[-2])
		a = s[N] % 1000000007
		return a * a % 1000000007


MOD = 1000000007

class Solution:

	def TotalWays(self, num):
		dp0 = 1
		dp1 = 1
		for i in range(1, num):
			ans1 = dp0 + dp1
			dp0 = dp1
			dp1 = ans1
		final = (dp0 + dp1) % MOD
		return final * final % MOD


class Solution:

	def TotalWays(self, N):
		b = 1
		s = 1
		for i in range(1, N):
			store = b
			b = s
			s = store + s
		return (b + s) ** 2 % (10 ** 9 + 7)


class Solution:

	def TotalWays(self, N):
		mod = 1000000007
		(b, s) = (1, 1)
		for i in range(1, N):
			(s, b) = (b + s, s)
		return (s + b) * (s + b) % mod


class Solution:

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


class Solution:

	def TotalWays(self, N):
		mod = 10 ** 9 + 7
		a = 1
		b = 1
		for i in range(2, N + 1):
			newa = (a + b) % mod
			newb = a
			a = newa
			b = newb
		ans = (a + b) % mod
		return ans ** 2 % mod


class Solution:

	def TotalWays(self, n):
		z = o = 1
		for i in range(1, n):
			tz = o % 1000000007
			to = z % 1000000007 + o % 1000000007
			o = to
			z = tz
		t = (o + z) % 1000000007
		return t * t % 1000000007


class Solution:

	def TotalWays(self, N):
		if N > 1000:
			return -1
		dpO = [0 for _ in range(0, N)]
		dpI = [0 for _ in range(0, N)]
		dpO[0] = 1
		dpI[0] = 1
		mod = 10 ** 9 + 7
		for i in range(1, N):
			dpO[i] = (dpO[i - 1] + dpI[i - 1]) % mod
			dpI[i] = dpO[i - 1]
		return (dpO[N - 1] + dpI[N - 1]) % mod * (dpO[N - 1] + dpI[N - 1]) % mod % mod


MOD = 1000000007

class Solution:

	def TotalWays(self, N):
		dp = [0] * (N + 1)
		dp[0] = dp[1] = 1
		for i in range(2, N + 1):
			dp[i] = dp[i - 1] + dp[i - 2]
			dp[i] %= MOD
		ans = dp[N - 1] + dp[N]
		ans %= MOD
		ans *= ans
		ans %= MOD
		return ans


class Solution:

	def TotalWays(self, N):
		a = 1
		b = 2
		if N == 1:
			return b ** 2
		else:
			for i in range(1, N):
				c = a + b
				a = b
				b = c
			ans = b ** 2
			return ans % 1000000007


class Solution:

	def TotalWays(self, N):
		mod = 1000000007
		(a, b) = (1, 1)
		for i in range(1, N):
			temp = (a + b) % mod
			b = a
			a = temp
		ans = (a + b) % mod
		return ans * ans % mod


class Solution:

	def TotalWays(self, N):
		buil = [0 for i in range(N + 1)]
		space = [0 for i in range(N + 1)]
		buil[N] = 1
		space[N] = 1
		for i in range(N - 1, -1, -1):
			buil[i] = space[i + 1]
			space[i] = space[i + 1] + buil[i + 1]
		return (buil[1] + space[1]) ** 2 % 1000000007


class Solution:

	def TotalWays(self, N):
		mod = 10 ** 9 + 7
		(one, two) = (1, 1)
		temp = 0
		for i in range(N):
			temp = one + two
			two = one
			one = temp
		return one ** 2 % mod


class Solution:

	def TotalWays(self, N):
		(s, b) = (1, 0)
		for _ in range(N):
			(b, s) = (s, s + b)
		x = (b + s) % 1000000007
		return x * x % 1000000007


from functools import lru_cache
from sys import setrecursionlimit as srl
srl(10 ** 6)

class Solution:

	def TotalWays(self, N):

		@lru_cache(None)
		def rec(x):
			if x >= N:
				return 1
			return (rec(x + 1) + rec(x + 2)) % 1000000007
		return pow(rec(0), 2, 1000000007)


class Solution:

	def TotalWays(self, N):
		os = ob = 1
		for i in range(2, N + 1):
			ns = os + ob
			nb = os
			(os, ob) = (ns, nb)
		x = (os + ob) % (10 ** 9 + 7)
		return x ** 2 % (10 ** 9 + 7)


class Solution:

	def TotalWays(self, N):
		dp = [[0] * (N + 1) for _ in range(2)]
		dp[0][1] = dp[1][1] = 1
		for i in range(2, N + 1):
			dp[0][i] = (dp[0][i - 1] + dp[1][i - 1]) % (10 ** 9 + 7)
			dp[1][i] = dp[0][i - 1] % (10 ** 9 + 7)
		x = (dp[0][N] + dp[1][N]) % (10 ** 9 + 7)
		return x ** 2 % (10 ** 9 + 7)


class Solution:

	def TotalWays(self, N):
		m = 1000000007
		x = {}

		def fib(n):
			if n == 0:
				return 1
			if n == 1:
				return 2
			if n in x:
				return x[n]
			else:
				x[n] = (fib(n - 1) % m + fib(n - 2) % m) % m
				return x[n]
		a = 0
		for i in range(1, N + 1):
			a = fib(i)
		return a * a % m


class Solution:

	def TotalWays(self, N):
		countS = 1
		countB = 1
		for i in range(2, N + 1):
			prevcountB = countB
			prevcountS = countS
			countS = prevcountB + prevcountS
			countB = prevcountS
		return (countB + countS) ** 2 % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


maj = int(1000000000.0 + 7)

class Solution:

	def TotalWays(self, N):
		prev1 = prev2 = 1
		for i in range(2, N + 2):
			temp = prev1 + prev2
			prev1 = prev2
			prev2 = temp
		return prev2 ** 2 % maj
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


class Solution:

	def TotalWays(self, N):
		m = 10 ** 9 + 7
		dp = [0, 2, 3] + [0] * (N - 2)
		for i in range(3, N + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % m
		return dp[N] * dp[N] % m
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


class Solution:

	def TotalWays(self, N):
		cob = 1
		cos = 1
		for i in range(2, N + 1):
			ncob = cos
			ncos = cos + cob
			cos = ncos
			cob = ncob
		return (cob + cos) ** 2 % (10 ** 9 + 7)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


class Solution:

	def TotalWays(self, N):
		b = 1
		s = 1
		m = 10 ** 9 + 7
		for i in range(1, N):
			(b, s) = (s, b + s)
			b = b % m
			s = s % m
		res = (b + s) % m
		return res * res % m
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


class Solution:

	def TotalWays(self, N):
		mod = 1000000007
		(b, s) = (1, 1)
		for i in range(1, N):
			temp = b
			b = s
			s = (temp + s) % mod
		return pow((b + s) % mod, 2) % mod
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


class Solution:

	def TotalWays(self, N):
		arr = [[0, 0] for _ in range(N)]
		arr[-1][0] = 1
		arr[-1][1] = 1
		for i in range(N - 2, -1, -1):
			arr[i][0] = arr[i + 1][1]
			arr[i][1] = arr[i + 1][0] + arr[i + 1][1]
			arr[i][0] %= 10 ** 9 + 7
			arr[i][1] %= 10 ** 9 + 7
		ans = arr[0][0] + arr[0][1]
		ans **= 2
		ans %= 10 ** 9 + 7
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


class Solution:

	def TotalWays(self, N):
		ocz = 1
		oco = 1
		for i in range(2, N + 1):
			ncz = oco
			nco = ocz + oco
			ocz = ncz
			oco = nco
		return (ocz + oco) * (ocz + oco) % (pow(10, 9) + 7)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalWays(N)
		print(ans)


class Solution:

	def TotalWays(self, N):
		pre = 1
		cur = 1
		for i in range(N - 1):
			x = cur + pre
			pre = cur
			cur = x
		return (pre + cur) ** 2 % 1000000007


class Solution:

	def TotalWays(self, N):
		space = 1
		building = 1
		for i in range(2, N + 1):
			curr_space = building + space
			curr_building = space
			space = curr_space
			building = curr_building
		ans = (space + building) ** 2
		return ans % (10 ** 9 + 7)


mod = 10 ** 9 + 7

class Solution:

	def TotalWays(self, N):
		if N == 0:
			return 0
		space = 1
		building = 1
		for i in range(2, N + 1):
			prev = space
			space = (space + building) % mod
			building = prev
		k = space + building
		k = k * k % mod
		return k


class Solution:

	def TotalWays(self, N):
		MOD = 1000000007
		(pb, ps, cb, cs) = (0, 0, 1, 1)
		for i in range(2, N + 1):
			(pb, ps) = (cb, cs)
			cb = ps % MOD
			cs = ps % MOD + pb % MOD
		t = (cs + cb) % MOD
		return int(t * t % MOD)


class Solution:

	def TotalWays(self, N):
		ob = 1
		os = 1
		for i in range(2, N + 1):
			nb = os
			ns = os + ob
			os = ns
			ob = nb
		ans = ob + os
		ans **= 2
		return ans % 1000000007


class Solution:

	def TotalWays(self, N):
		l = [1, 2]
		for i in range(N):
			l.append(l[-1] + l[-2])
		r = l[N] % 1000000007
		return r ** 2 % 1000000007


class Solution:

	def TotalWays(self, N):
		dp = [1, 2, 3]
		for i in range(3, N + 1):
			dp.append((dp[-1] % 1000000007 + dp[-2] % 1000000007) % 1000000007)
		return dp[N] ** 2 % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 1:
			return 4
		if N == 2:
			return 9
		if N == 3:
			return 25
		a1 = 2
		a2 = 3
		for i in range(N - 2):
			t = a2
			a2 = a2 + a1
			a1 = t
		return a2 % 1000000007 * (a2 % 1000000007) % 1000000007


class Solution:

	def TotalWays(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 4
		result = 0
		S = 1
		B = 1
		for i in range(1, N):
			nB = S
			nS = B + S
			S = nS
			B = nB
		result = B + S
		return result ** 2 % (10 ** 9 + 7)


class Solution:

	def TotalWays(self, N):
		buil = 1
		space = 1
		for i in range(2, N + 1):
			prevB = buil
			prevSpace = space
			buil = prevSpace
			space = prevB + prevSpace
		total = buil + space
		return total * total % 1000000007


class Solution:

	def TotalWays(self, N):
		mod = 1000000007
		zero = 1
		one = 1
		sums = zero + one
		for i in range(2, N + 1):
			one = zero
			zero = sums
			sums = one + zero
		return pow(sums, 2) % mod


def compute(dp, N, i, j):
	if i == N:
		dp[i][j] = 1
		return
	if j == 0:
		if dp[i + 1][1] == -1:
			compute(dp, N, i + 1, 1)
		dp[i][j] = dp[i + 1][1]
	else:
		if dp[i + 1][1] == -1:
			compute(dp, N, i + 1, 1)
		if dp[i + 1][0] == -1:
			compute(dp, N, i + 1, 0)
		dp[i][j] = dp[i + 1][1] % 1000000007 + dp[i + 1][0] % 1000000007
		dp[i][j] %= 1000000007
import sys

class Solution:

	def TotalWays(self, N):
		t = 1000000007
		sys.setrecursionlimit(10 ** 6)
		dp = [[-1 for i in range(2)] for j in range(N + 1)]
		compute(dp, N, 1, 0)
		compute(dp, N, 1, 1)
		tem = dp[1][0] % t + dp[1][1] % t
		tem %= t
		tem *= tem
		tem %= t
		return tem