There are N points on the road ,you can step ahead by 1 or 2 . Find the number of ways you can reach at point N. 
Example 1:
Input: N = 4
Output: 5
Explanation: Three ways to reach at 4th
point. They are {1, 1, 1, 1}, {1, 1, 2},
{1, 2, 1} {2, 1, 1}, {2, 2}.
Example 2:
Input: N = 5
Output: 8
Explanation: Three ways to reach at 5th
point. They are {1, 1, 1, 1, 1},
{1, 1, 1, 2}, {1, 1, 2, 1}, {1, 2, 1, 1},
{2, 1, 1, 1}{1, 2, 2}, {2, 1, 2}, {2, 2, 1}
Your Task:
You don't need to read or print anyhting. Your task is to complete the function nthPoint() which takes N as input parameter and returns the total number of ways modulo 10^{9} + 7 to reach at Nth point.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def nthPoint(self,n):

		# Code here

Solutions:
class Solution:
	mod = 10 ** 9 + 7

	def nthPoint(self, n):
		if n <= 0:
			return 0
		if n <= 1:
			return 1
		if n <= 2:
			return 2
		ways = [0] * (n + 1)
		ways[1] = 1
		ways[2] = 2
		for i in range(3, n + 1):
			ways[i] = (ways[i - 1] % self.mod + ways[i - 2]) % self.mod
		return ways[n]


class Solution:

	def nthPoint(self, n):
		first = 0
		second = 1
		for i in range(n):
			ways = (first + second) % 1000000007
			first = second
			second = ways
		return ways


class Solution:

	def nthPoint(self, n):
		MOD = 10 ** 9 + 7
		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 - 2] + dp[i - 1]) % MOD
		return dp[n]


class Solution:

	def nthPoint(self, n):
		dp = [0 for i in range(n + 1)]

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def nthPoint(self, n):
		ans = [1, 2]
		mod = 10 ** 9 + 7
		if n == 1 or n == 2:
			return n
		for i in range(2, n):
			ans.append((ans[-1] + ans[-2]) % mod)
		return ans[-1]


def dynamic(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]
	return dp[n] % (10 ** 9 + 7)

class Solution:

	def nthPoint(self, n):
		return dynamic(n)
		return len(stack)


class Solution:

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


class Solution:

	def nthPoint(self, n):
		m = 10 ** 9 + 7
		l = [-1] * (10 ** 4 + 3)

		def f(n):
			if n == 1:
				return 1
			if n == 2:
				return 2
			if l[n] != -1:
				return l[n]
			l[n] = f(n - 1) % m + f(n - 2) % m
			return l[n] % m
		return f(n) % m


class Solution:

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


class Solution:

	def nthPoint(self, n):
		n1 = 1
		n2 = 2
		s1 = 0
		for i in range(2, n + 1):
			s1 = n1 + n2
			n1 = n2
			n2 = s1
		return n1 % 1000000007


class Solution:

	def nthPoint(self, n):
		dp = [-1] * n

		def fun(i):
			if i == n:
				return 1
			if i > n:
				return 0
			if dp[i] != -1:
				return dp[i]
			dp[i] = (fun(i + 1) % 1000000007 + fun(i + 2) % 1000000007) % 1000000007
			return dp[i]
		return fun(0)


class Solution:

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


class Solution:

	def nthPoint(self, n):
		d = {1: 1, 2: 2}
		for i in range(3, n + 1):
			d[i] = (d[i - 1] + d[i - 2]) % (10 ** 9 + 7)
		return d[n]


mod = 1000000007

class Solution:

	def solve_without_DP(self, n):
		if n == 0:
			return 1
		if n < 0:
			return 0
		return (self.solve_without_DP(n - 1) + self.solve_without_DP(n - 2)) % mod

	def solve_with_DP(self, n, memory):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if memory[n] != -1:
			return memory[n]
		memory[n] = (self.solve_with_DP(n - 1, memory) + self.solve_with_DP(n - 2, memory)) % mod
		return memory[n]

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

	def top_down(self, n):
		memory = [-1] * (n + 1)
		return self.solve_with_DP(n, memory)

	def optimized_Bottom_up(self, n):
		if n == 1:
			return 1
		point_0 = 1
		point_1 = 1
		ans = 0
		for i in range(2, n + 1):
			ans = (point_0 + point_1) % mod
			point_0 = point_1
			point_1 = ans
		return ans

	def nthPoint(self, n):
		return self.optimized_Bottom_up(n)


mod = 1000000007

class Solution:

	def solve_without_DP(self, n):
		if n == 0:
			return 1
		if n < 0:
			return 0
		return (self.solve_without_DP(n - 1) + self.solve_without_DP(n - 2)) % mod

	def solve_with_DP(self, n, memory):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if memory[n] != -1:
			return memory[n]
		memory[n] = (self.solve_with_DP(n - 1, memory) + self.solve_with_DP(n - 2, memory)) % mod
		return memory[n]

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

	def top_down(self, n):
		memory = [-1] * (n + 1)
		return self.solve_with_DP(n, memory)

	def nthPoint(self, n):
		return self.solve_Bottom_Up(n)


mod = 1000000007

class Solution:

	def solve_without_DP(self, n):
		if n == 0:
			return 1
		if n < 0:
			return 0
		return (self.solve_without_DP(n - 1) + self.solve_without_DP(n - 2)) % mod

	def solve_with_DP(self, n, memory):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if memory[n] != -1:
			return memory[n]
		memory[n] = (self.solve_with_DP(n - 1, memory) + self.solve_with_DP(n - 2, memory)) % mod
		return memory[n]

	def nthPoint(self, n):
		memory = [-1] * (n + 1)
		return self.solve_with_DP(n, memory)


class Solution:

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


class Solution:

	def fib(n, dp):
		dp = [0] * (n + 1)

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


class Solution:

	def getNthPointMemo(self, n, dp):
		if n == 0 or n == 1:
			return 1
		if dp[n] != -1:
			return dp[n]
		take_two_step = self.getNthPointMemo(n - 2, dp)
		take_one_step = self.getNthPointMemo(n - 1, dp)
		dp[n] = take_one_step + take_two_step
		return dp[n]

	def nthPoint(self, n):
		dp = [-1 for i in range(n + 1)]
		return self.getNthPointMemo(n, dp) % (pow(10, 9) + 7)


class Solution:

	def nthPoint(self, n):
		dp = [-1 for i in range(n + 1)]
		res = self.func(n, dp)
		return res % 1000000007

	def func(self, n, dp):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		dp[n] = self.func(n - 1, dp) + self.func(n - 2, dp)
		return dp[n]
x = Solution()
n = 4
x.nthPoint(n)


class Solution:

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


class Solution:

	def nthPoint(self, n):
		lst = [-1] * (n + 1)
		mod = 10 ** 9 + 7

		def solve(n):
			if n == 1:
				return 1
			if n == 2:
				return 2
			if lst[n] != -1:
				return lst[n]
			else:
				lst[n] = (solve(n - 1) % mod + solve(n - 2) % mod) % mod
				return lst[n]
		return solve(n)


class Solution:

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


class Solution:

	def nthPoint(self, n):
		dp = [-1] * (n + 1)
		mod = 10 ** 9 + 7

		def count(dp, n):
			if n <= 2:
				return n
			if n < 0:
				return 0
			if dp[n] == -1:
				dp[n] = count(dp, n - 1) + count(dp, n - 2)
			return dp[n] % mod
		return count(dp, n)


class Solution:

	def nthPoint(self, n):
		dp = []
		dp.append(1)
		dp.append(1)
		for i in range(2, n + 1):
			dp.append(int((dp[i - 1] + dp[i - 2]) % (1000000000.0 + 7)))
		return dp[n]


class Solution:

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


class Solution:

	def nthPoint(self, n):
		mod = 10 ** 9 + 7
		if n <= 1:
			return 1
		(prev1, prev2) = (2, 1)
		for i in range(2, n):
			cur = (prev1 + prev2) % mod
			prev2 = prev1
			prev1 = cur
		return prev1


class Solution:

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


class Solution:

	def solve(self, n, dp):
		if n <= 1:
			return 1
		if dp[n] != -1:
			return dp[n]
		dp[n] = self.solve(n - 1, dp) + self.solve(n - 2, dp)
		dp[n] = dp[n] % (10 ** 9 + 7)
		return dp[n]

	def nthPoint(self, n):
		dp = [-1 for i in range(n + 1)]
		return self.solve(n, dp)


class Solution:

	def nthPoint(self, n):
		one = 1
		two = 1
		for i in range(n - 1):
			temp = one
			one = one + two
			two = temp
		return one % 1000000007


class Solution:

	def nthPoint(self, n):
		hm = {}
		return self.np(n, hm)

	def np(self, n, hm):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if hm.get(n):
			return hm[n]
		a = self.np(n - 1, hm)
		b = self.np(n - 2, hm)
		hm[n] = (a + b) % 1000000007
		return (a + b) % 1000000007


class Solution:

	def nthPoint(self, n):

		def my(n):
			if n == 1 or n == 2:
				return n
			if dp[n] != -1:
				return dp[n]
			dp[n] = (my(n - 1) + my(n - 2)) % 1000000007
			return dp[n]
		dp = [-1] * (n + 1)
		return my(n)


class Solution:

	def nthPoint(self, n):

		def count(n, dp):
			if n < 0:
				return 0
			if n == 0:
				return 1
			if dp[n] != -1:
				return dp[n]
			l = count(n - 1, dp)
			r = count(n - 2, dp)
			dp[n] = (l + r) % 1000000007
			return dp[n]
		dp = [-1] * (n + 1)
		return count(n, dp)


class Solution:

	def nthfib(self, n, p):
		if n <= 1:
			p[n] = 1
			return 1
		if p[n] != -1:
			return p[n]
		p[n] = Solution().nthfib(n - 1, p) + Solution().nthfib(n - 2, p)
		return p[n]

	def nthPoint(self, n):
		p = [-1] * (n + 1)
		Solution().nthfib(n, p)
		return p[n] % (10 ** 9 + 7)


class Solution:

	def nthPoint(self, n):
		prev1 = 2
		prev2 = 1
		if n <= 2:
			return n
		for i in range(3, n + 1):
			res = prev1 + prev2
			prev2 = prev1
			prev1 = res
		return prev1 % (10 ** 9 + 7)


class Solution:

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


class Solution:

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


class Solution:

	def count(self, n, Db):
		if n == 0 or n == 1:
			return 1
		if n < 0:
			return 0
		if Db[n] != -1:
			return Db[n]
		Two = 0
		One = self.count(n - 1, Db)
		if n > 1:
			Two = self.count(n - 2, Db)
		Db[n] = One + Two
		return Db[n]

	def nthPoint(self, n):
		Db = [-1] * (n + 1)
		return self.count(n, Db) % 1000000007


class Solution:

	def nthPoint(self, n):
		n = n + 1
		Fab = [0, 1]

		def f(n):
			if n < 0:
				return
			if n < len(Fab):
				return Fab[n]
			else:
				Fab.append(f(n - 1) + f(n - 2))
			return Fab[n]
		return f(n) % 1000000007


class Solution:

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


class Solution:

	def nthPoint(self, n):
		t = [-1 for i in range(n + 1)]
		return self.helper(n, t)

	def helper(self, n, t):
		mod = 10 ** 9 + 7
		if n < 0:
			return 0
		if n == 0 or n == 1:
			return 1
		if t[n] != -1:
			return t[n] % mod
		jump1 = self.helper(n - 1, t)
		jump2 = self.helper(n - 2, t)
		t[n] = (jump1 + jump2) % mod
		return t[n] % mod


class Solution:

	def nthPoint(self, n):
		v = [1, 2]
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			for j in range(0, len(v)):
				if v[j] <= i:
					dp[i] = dp[i] + dp[i - v[j]]
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def nthPoint(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		else:
			a = 1
			b = 2
			for i in range(3, n + 1):
				new = a + b
				a = b
				b = new
			return b % 1000000007


class Solution:

	def count(self, n, dp):
		if dp[n] != -1:
			return dp[n]
		if n == 0:
			return 1
		if n in [1, 2]:
			return n
		if n < 0:
			return 0
		if dp[n - 1] == -1:
			dp[n - 1] = self.count(n - 1, dp)
		if dp[n - 2] == -1:
			dp[n - 2] = self.count(n - 2, dp)
		dp[n] = dp[n - 1] + dp[n - 2]
		return dp[n]

	def nthPoint(self, n):
		dp = [-1] * (n + 1)
		ans = self.count(n, dp)
		k = int(1000000000.0 + 7)
		return ans % k


class Solution:

	def __init__(self):
		self.dictAns = {}

	def nthPoint(self, n):
		if n == 1 or n == 2:
			return n
		if n in self.dictAns:
			return self.dictAns[n]
		ans = self.nthPoint(n - 1) + self.nthPoint(n - 2)
		self.dictAns[n] = ans
		return ans % (10 ** 9 + 7)


class Solution:

	def nthPoint(self, n):
		m = 2
		res = [0 for x in range(n + 1)]
		(res[0], res[1]) = (1, 1)
		for i in range(2, n + 1):
			j = 1
			while j <= m and j <= i:
				res[i] = res[i] + res[i - j]
				j = j + 1
		return res[n] % 1000000007


class Solution:

	def nthPoint(self, n):
		m = 10 ** 9 + 7
		dp = [0 for i in range(n + 1)]
		try:
			dp[0] = 1
			dp[1] = 1
			dp[2] = 2
		except:
			if n == 0:
				return 1
			return n
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] % m + dp[i - 2] % m) % m
		return dp[n] % m


class Solution:

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


class Solution:

	def nthPoint(self, n):
		dp = [-1] * (n + 1)
		mod = 10 ** 9 + 7

		def solve(n):
			if n <= 1:
				return 1
			if dp[n] != -1:
				return dp[n]
			dp[n] = (solve(n - 1) % mod + solve(n - 2) % mod) % mod
			return dp[n]
		return solve(n)


class Solution:

	def nthPoint(self, n):
		mod = 10 ** 9 + 7
		if n == 0 or n == 1:
			return 1
		p1 = 1
		p2 = 1
		for i in range(2, n + 1):
			curr = (p1 + p2) % mod
			p2 = p1
			p1 = curr
		return p1


class Solution:

	def nthPoint(self, n):

		def helper(n, memo={}):
			mod = 1000000007
			if n in memo:
				return memo[n]
			if n <= 2:
				return 1
			memo[n] = (helper(n - 1, memo) + helper(n - 2, memo)) % mod
			return memo[n]
		return helper(n + 1)
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.nthPoint(n)
		print(ans)


class Solution:

	def nthPoint(self, n):
		m = 1000000007
		rak = [-1 for i in range(n + 1)]
		rak[0] = 1
		rak[1] = 1
		for i in range(2, n + 1):
			rak[i] = (rak[i - 1] + rak[i - 2]) % m
		return rak[n]
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.nthPoint(n)
		print(ans)


class Solution:

	def nthPoint(self, n):

		def recursion(ind):
			if ind in dp:
				return dp[ind]
			if ind == n:
				return 1
			if ind > n:
				return 0
			one = recursion(ind + 1)
			two = recursion(ind + 2)
			dp[ind] = one + two
			return dp[ind]
		dp = {}
		MOD = 10 ** 9 + 7
		return recursion(0) % MOD
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.nthPoint(n)
		print(ans)


class Solution:

	def nthPoint(self, n):
		dp = [-1 for i in range(n + 1)]
		mod = 1000000000.0 + 7
		(dp[0], dp[1]) = (1, 1)
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
		return int(dp[n] % mod)
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.nthPoint(n)
		print(ans)


class Solution:

	def nthPoint(self, n):

		def main(n):
			d = {}

			def fib(n, d):
				if n in (0, 1):
					return n
				elif n in d:
					return d[n]
				else:
					d[n] = fib(n - 1, d) + fib(n - 2, d)
					return d[n]
			return fib(n, d)
		return main(n + 1) % (10 ** 9 + 7)
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.nthPoint(n)
		print(ans)


class Solution:

	def nthPoint(self, n):
		(a, b) = (1, 1)
		for i in range(2, n + 1):
			curr = a + b
			b = a
			a = curr
		return a % 1000000007
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.nthPoint(n)
		print(ans)


class Solution:

	def nthPoint(self, n):

		def check(i):
			if i == 1:
				return 1
			if i == 2:
				return 2
			if dp[i] != -1:
				return dp[i]
			dp[i] = check(i - 1) + check(i - 2)
			return dp[i]
		dp = [-1 for i in range(n + 1)]
		return check(n) % 1000000007
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.nthPoint(n)
		print(ans)