Given a positive integer n, find the nth fibonacci number. Since the answer can be very large, return the answer modulo 1000000007.
Example 1:
Input: n = 2
Output: 1 
Explanation: 1 is the 2nd number
of fibonacci series.
Example 2:
Input: n = 5
Output: 5
Explanation: 5 is the 5th number
of fibonacci series.
Your Task:  
You dont need to read input or print anything. Complete the function nthFibonacci() which takes n as input parameter and returns nth fibonacci number.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1<= n <=1000

Difficulty: EASY
Tags: Dynamic programming

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

Starter code:
#User function Template for python3



class Solution:

    def nthFibonacci(self, n):

        # code here 

Solutions:
import sys
sys.setrecursionlimit(10 ** 4)

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def nthFibonacci(self, n):
		fib = [0, 1]
		if n <= 1:
			return n
		else:
			for i in range(2, n + 1):
				fib.append(fib[i - 1] + fib[i - 2])
			return fib[n] % 1000000007


class Solution:

	def nthFibonacci(self, n):
		a = b = 1
		if n == 1 or n == 2:
			return 1
		else:
			for i in range(n - 2):
				z = a + b
				a = b
				b = z
			return z % 1000000007


class Solution:

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


class Solution:

	def nthFibonacci(self, n, memo={}):
		if n in memo.keys():
			return memo[n] % 1000000007
		if n <= 2:
			return 1
		memo[n] = Solution.nthFibonacci(self, n - 1, memo) + Solution.nthFibonacci(self, n - 2, memo)
		return memo[n] % 1000000007


class Solution:

	def nthFibonacci(self, n):
		dp = [-1] * (n + 1)
		return self.fib(n, dp)

	def fib(self, n, dp):
		if n <= 1:
			return n
		if dp[n] != -1:
			return dp[n]
		dp[n] = self.fib(n - 1, dp) + self.fib(n - 2, dp)
		return dp[n] % 1000000007


class Solution:

	def nthFibonacci(self, n):
		assert n >= 0
		if n <= 1:
			return n
		f1 = 0
		f = 1
		for i in range(2, n + 1):
			tmpf = f
			f += f1
			f1 = tmpf
		return f % 1000000007


class Solution:

	def nthFibonacci(self, n):
		fibo = [0, 1]
		for i in range(n - 1):
			fibo = [fibo[1], sum(fibo)]
		return fibo[1] % 1000000007


class Solution:

	def nthFibonacci(self, n):
		memo = {}

		def helper(n):
			if n in memo:
				return memo[n]
			if n == 0:
				memo[n] = 0
				return 0
			if n == 1:
				memo[n] = 1
				return 1
			memo[n] = (helper(n - 1) + helper(n - 2)) % 1000000007
			return memo[n]
		return helper(n)


class Solution:

	def nthFibonacci(self, n):
		if n <= 1:
			return n
		prev2 = 0
		prev1 = 1
		res = 0
		for i in range(2, n + 1):
			res = prev1 + prev2
			prev2 = prev1
			prev1 = res
		return res % 1000000007


class Solution:

	def nthFibonacci(self, n):
		if n == 1 or n == 0 or n == 2:
			return 1
		else:
			dp = []
			for i in range(n + 1):
				dp.append(0)
			dp[0] = 1
			dp[1] = 1
			dp[2] = 1
			for j in range(3, n + 1):
				dp[j] += dp[j - 1] + dp[j - 2]
			return dp[n] % 1000000007


class Solution:
	F = [-1 for i in range(1, 10001)]

	def nthFibonacci(self, n):
		if n == 1 or n == 0:
			return n
		if self.F[n] != -1:
			return self.F[n] % 1000000007
		else:
			self.F[n] = self.nthFibonacci(n - 1) + self.nthFibonacci(n - 2)
			return self.F[n] % 1000000007


class Solution:

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


MOD = 10 ** 9 + 7

def fib(n, memo={}):
	if n in memo:
		return memo[n]
	elif n < 3:
		memo[n] = 1
	else:
		memo[n] = (fib(n - 1) + fib(n - 2)) % MOD
	return memo[n]

class Solution:

	def nthFibonacci(self, n):
		return fib(n)


class Solution:

	def nthFibonacci(self, n):
		fir = 0
		sec = 1
		for i in range(n + 1):
			sm = fir + sec
			fir = sec
			sec = sm
			if i == n - 1:
				return fir % 1000000007
		return fir


class Solution:

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


class Solution:

	def nthFibonacci(self, n):
		l = [0, 1]
		modulo = 1000000007
		for i in range(1, n + 1):
			sumi = l[i - 1] + l[i]
			l.append(sumi)
		return l[n] % modulo


class Solution:

	def nthFibonacci(self, n):
		x = 1
		y = 1
		a = 0
		if n == 1 or n == 2:
			return 1
		else:
			for i in range(2, n):
				a = x + y
				x = y
				y = a
			return a % 1000000007


class Solution:

	def nthFibonacci(self, n):
		a = 0
		b = 1
		c = a + b
		for g in range(n):
			a = b
			b = c
			c = a + b
		return a % 1000000007


class Solution:

	def nthFibonacci(self, n):
		i = 0
		c = 1
		j = 1
		b = i + j
		while c < n:
			b = i + j
			i = j
			j = b
			c += 1
		return b % 1000000007


import numpy as np

class Solution:

	def nthFibonacci(self, n):
		f = np.zeros(n + 1)
		f[0] = 0
		f[1] = 1
		if n <= 1:
			return int(f[n])
		for i in range(2, n + 1):
			f[i] = (f[i - 1] + f[i - 2]) % 1000000007
		return int(f[n])


class Solution:

	def nthFibonacci(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if n == 2:
			return 1
		t1 = 1
		t2 = 1
		for i in range(2, n):
			sum = t1 + t2
			t1 = t2
			t2 = sum
		return sum % 1000000007


class Solution:

	def nthFibonacci(self, n):
		cache = {}

		def fib(i):
			if i in cache:
				return cache[i]
			if i <= 2:
				return 1
			res = fib(i - 1) + fib(i - 2)
			cache[i] = res
			return res
		return fib(n) % 1000000007

		def fibo(i):
			if i <= 2:
				return 1
			return fibo(i - 1) + fibo(i - 2)
		return fibo(n) % 1000000007
		a = b = 1
		c = 0
		for i in range(n - 2):
			c = a + b
			a = b
			b = c
		return c % 1000000007


class Solution:

	def nthFibonacci(self, n):
		cache = {}

		def fib(i):
			if i in cache:
				return cache[i]
			if i <= 2:
				return 1
			res = fib(i - 1) + fib(i - 2)
			cache[i] = res
			return res
		return fib(n) % 1000000007


class Solution:

	def nthFibonacci(self, n):
		n1 = 0
		n2 = 1
		if n == 1 or n == 2:
			return 1
		else:
			for i in range(2, n + 1):
				s = n1 + n2
				n1 = n2
				n2 = s
			return s % 1000000007


class Solution:

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


class Solution:

	def nthFibonacci(self, n):
		if n <= 1:
			return n

		def do_math(i_minus_2, i_minus_1, count, n):
			this_sum = i_minus_2 + i_minus_1
			if count == n:
				return this_sum
			count += 1
			return do_math(i_minus_1, i_minus_2 + i_minus_1, count, n)
		return do_math(0, 1, 2, n) % 1000000007


class Solution:

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


class Solution:

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


class Solution:

	def nthFibonacci(self, n):
		dp = {}

		def fib(a):
			if a in dp:
				return dp[a]
			if a <= 1:
				return a
			else:
				dp[a] = fib(a - 1) + fib(a - 2)
				return dp[a]
		return fib(n) % 1000000007


class Solution:

	def nthFibonacci(self, n):
		_a = 0
		_b = 1
		for _ in range(1, n):
			temp = _b
			_b = _b + _a
			_a = temp
		return _b % 1000000007


class Solution:

	def nthFibonacci(self, n):
		(a, b) = (0, 1)
		for i in range(n - 1):
			(a, b) = (b, (a + b) % 1000000007)
		return b


class Solution:

	def nthFibonacci(self, n):
		mod = 1000000007
		first = 0
		sec = 1
		if n == 0:
			return 0
		if n == 1:
			return 1
		third = [0]
		while n - 1:
			third[0] = first + sec
			first = sec
			sec = third[0]
			n -= 1
		return third[0] % mod


class Solution:

	def nthFibonacci(self, n):
		mod = 1000000007
		if n < 2:
			return n
		(prev, curr) = (0, 1)
		for _ in range(2, n + 1):
			c = prev + curr
			c %= mod
			prev = curr
			curr = c
		return c


class Solution:

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


class Solution:

	def nthFibonacci(self, n):
		first = 0
		second = 1
		if n == 0 or n == 1:
			return n
		for i in range(2, n + 1):
			res = (first + second) % 1000000007
			first = second
			second = res
		return res


class Solution:

	def nthFibonacci(self, n):
		dp = [0, 1]
		for i in range(2, n + 1):
			curr_number = dp[i - 1] + dp[i - 2]
			dp.append(curr_number % 1000000007)
		return dp[-1]


class Solution:

	def nthFibonacci(self, n):
		prev2 = 0
		prev = 1
		for i in range(2, n + 1):
			curr = prev + prev2
			prev2 = prev
			prev = curr
		return prev % 1000000007


class Solution:

	def nthFibonacci(self, n):
		if n == 0 or n == 1:
			return n
		n = n - 1
		v1 = 0
		v2 = 1
		fib = v1 + v2
		while n:
			fib = (v1 + v2) % 1000000007
			v1 = v2
			v2 = fib
			n -= 1
		return fib


class Solution:

	def __init__(self):
		self.dp = [-1 for i in range(1, 1000 + 2)]
		self.mod = 1000000007

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


class Solution:

	def nthFibonacci(self, n):
		fibNumbers = []
		for index in range(1, n + 1):
			if index < 3:
				fibNumbers.append(1)
				continue
			fibN = fibNumbers[index - 2] + fibNumbers[index - 3]
			fibNumbers.append(fibN)
		return fibNumbers[index - 1] % 1000000007


class Solution:

	def nthFibonacci(self, n):
		if n <= 2:
			return 1
		first = 1
		second = 1
		for i in range(3, n + 1):
			temp = first
			first = second
			second = (temp + second) % 1000000007
		return second


class Solution:
	fib_cache = dict()

	def nthFibonacci(self, n):
		if n in self.fib_cache:
			return self.fib_cache[n]
		if n == 1 or n == 2:
			val = 1
		elif n > 2:
			val = self.nthFibonacci(n - 1) + self.nthFibonacci(n - 2)
		self.fib_cache[n] = val % 1000000007
		return val % 1000000007


class Solution:

	def nthFibonacci(self, n):
		if n == 1 or n == 2:
			return 1
		else:
			l = [1, 1]
			j = 1
			for i in range(n - 2):
				l.append(l[j] + l[j - 1])
				j += 1
			return l[n - 1] % 1000000007


class Solution:

	def nthFibonacci(self, n):
		stack = [0, 1]
		for i in range(2, n + 1):
			stack.append(stack[i - 1] + stack[i - 2])
		num = stack[n] % 1000000007
		return num


class Solution:

	def nthFibonacci(self, n):
		l = [-1] * (n + 1)

		def fib(a, l):
			if a <= 1:
				return a
			if l[a] != -1:
				return l[a]
			l[a] = fib(a - 1, l) + fib(a - 2, l)
			return l[a]
		return fib(n, l) % 1000000007


class Solution:

	def nthFibonacci(self, n):

		def func(n, d={}):
			if n in d:
				return d[n] % 1000000007
			if n == 1 or n == 2:
				return 1
			if n - 1 in d:
				n1 = d[n - 1]
			else:
				n1 = func(n - 1)
				d[n - 1] = n1
			if n - 2 in d:
				n2 = d[n - 2]
			else:
				n2 = func(n - 2)
				d[n - 2] = n2
			d[n] = n1 + n2
			return (n1 + n2) % 1000000007
		return func(n)


class Solution:

	def nthFibonacci(self, n):
		if n == 0:
			return 0
		elif n == 1:
			return 1
		else:
			temp_n = n - 2
			a = 0
			b = 1
			result = 0
			while temp_n >= 0:
				result = a + b
				a = b
				b = result
				temp_n -= 1
			return result % 1000000007