A Padovan Sequence is a sequence which is represented by the following recurrence relation
P(N) = P(N-2) + P(N-3)
P(0) = P(1) = P(2) = 1
Given a number N, find the N^{th} number in this sequence.
Note: Since the output may be very large, compute the answer modulus 10^9+7.
Example 1:
Input:
N = 3
Output: 2
Explanation: P_{1} + P_{0} = P3
P_{1 }= 1 and P_{0} = 1
Ã¢â¬â¹Example 2:
Input: 
N = 4
Output: 2
Explanation: P_{2} + P_{1} = P_{4}
_{ }P2 = 1 and P_{1} = 1
Your Task:
You don't need to read input or print anything. Your task is to complete the function padovanSequence() which takes integer N as input parameter and return N^{th} number in Padovan Sequence.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{6}

Difficulty: EASY
Tags: Number theory

Dynamic programming

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

Starter code:
#User function Template for python3



class Solution:

    def padovanSequence(self, n):

        # code here 

Solutions:
class Solution:

	def padovanSequence(self, n):
		if n == 0 or n == 1 or n == 2:
			return 1
		dp = [-1 for i in range(n + 1)]
		dp[0] = 1
		dp[1] = 1
		dp[2] = 1
		for i in range(3, n + 1):
			dp[i] = dp[i - 2] + dp[i - 3]
		return dp[n]


class Solution:

	def padovanSequence(self, n):
		preprecurrent = 1
		precurrent = 1
		prenext = 1
		re = 1
		for i in range(3, n + 1):
			re = preprecurrent + precurrent
			preprecurrent = precurrent
			precurrent = prenext
			prenext = re
		return re


class Solution:

	def padovanSequence(self, n):
		k = [1, 1, 1, 2, 2, 3, 4, 5]
		if n > 2:
			k = k[:n]
			while len(k) <= n:
				d = k[-2] + k[-3]
				k.append(d)
			return k[n]
		else:
			return k[n]


import math

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def padovanSequence(self, n):
		if n == 0 or n == 1 or n == 2:
			return 1
		return self.padovanSequence(n - 2) + self.padovanSequence(n - 3)


class Solution:

	def padovanSequence(self, n):
		p = {0: 1, 1: 1, 2: 1}
		if n <= 2 and n >= 0:
			return p[n]
		else:
			for i in range(3, n + 1):
				p[i] = p[i - 2] + p[i - 3]
			return p[n]


class Solution:

	def padovanSequence(self, n):
		m = 10 ** 9 + 7

		def seq(n):
			if n == 0 or n == 1 or n == 2:
				return 1
			else:
				return seq(n - 2) + seq(n - 3)
		return seq(n) % m


class Solution:

	def padovanSequence(self, n):

		def sol(n):
			if n == 0 or n == 1 or n == 2 or (n < 0):
				return 1
			else:
				return sol(n - 2) + sol(n - 3)
		k = sol(n)
		return k % (10 ** 9 + 7)


class Solution:

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


class Solution:

	def padovanSequence(self, n):
		prepre = pre = pcurr = 1
		pnext = 1
		for i in range(3, n + 1):
			pnext = prepre + pre
			prepre = pre
			pre = pcurr
			pcurr = pnext
		return pnext


class Solution:

	def padovanSequence(self, n):
		MOD = 10 ** 9 + 7
		(a, b, c) = (1, 1, 1)
		while n:
			(a, b, c) = (b, c, (a + b) % MOD)
			n -= 1
		return a


class Solution:

	def padovanSequence(self, n):
		l = [1, 1, 1]
		a = b = c = 1
		for i in range(2, n):
			d = a + b
			l.append(d)
			a = b
			b = c
			c = d
		return l[n] % 1000000007


class Solution:

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


class Solution:

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


class Solution:

	def padovanSequence(self, n):
		d = {}

		def helper(n):
			m = 1000000007
			if n == 0 or n == 1 or n == 2:
				return 1
			else:
				if n in d:
					return d[n]
				d[n] = helper(n - 2) % m + helper(n - 3) % m
				return d[n] % m
		return helper(n)


class Solution:

	def padovanSequence(self, N):
		F0 = 1
		F1 = 1
		F2 = 1
		F = 1
		for i in range(3, N + 1):
			F = F1 + F0
			F0 = F1
			F1 = F2
			F2 = F
		return F


class Solution:

	def padovanSequence(self, n):
		if n < 3:
			return 1
		x = y = z = 1
		for i in range(n - 2):
			t = z
			z = x + y
			x = y
			y = t
		return z


class Solution:

	def padovanSequence(self, n: int) -> int:
		from typing import Iterator

		def generator() -> Iterator[int]:
			a = b = c = 1
			while True:
				yield a
				(a, b, c) = (b, c, a + b)
		gen = generator()
		for _ in range(n):
			next(gen)
		result = next(gen) % 1000000007
		return result


class Solution:

	def padovanSequence(self, n):
		a = [1] * 10 ** 6
		for i in range(3, n + 1):
			a[i] = a[i - 2] + a[i - 3]
		return a[n]
		return a


class Solution:

	def padovanSequence(self, n):
		if n <= 2:
			return 1
		return self.padovanSequence(n - 2) + self.padovanSequence(n - 3)


class Solution:

	def padovanSequence(self, n):
		if n == 1 or n == 0 or n == 2:
			return 1
		a = 1
		b = 1
		c = 1
		for i in range(2, n):
			r = b
			k = c
			c = b + a
			b = k
			a = r
		return c % (10 ** 9 + 7)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.padovanSequence(n))


class Solution:

	def padovanSequence(self, n):
		(a, b, c, d) = (1, 1, 1, 1)
		for i in range(3, n + 1):
			d = a + b
			a = b
			b = c
			c = d
		return d % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.padovanSequence(n))


class Solution:

	def padovanSequence(self, n):
		pad0 = 1
		pad1 = 1
		pad2 = 2
		if n == 0:
			return 1
		if n == 1:
			return 1
		if n == 2:
			return 1
		if n == 3:
			return 2
		series = 0
		for i in range(3, n):
			series = pad0 + pad1
			pad0 = pad1
			pad1 = pad2
			pad2 = series
		return series % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.padovanSequence(n))


class Solution:

	def padovanSequence(self, n):
		l = [1, 1, 1]
		for i in range(3, n + 1):
			l.append(l[-2] + l[-3])
		return l[n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.padovanSequence(n))


class Solution:

	def padovanSequence(self, n):
		m = 1000000000.0 + 7
		p = p1 = p2 = ans = 1
		for i in range(3, n + 1):
			ans = (p + p1) % m
			(p, p1, p2) = (p1, p2, ans)
		return int(ans)


class Solution:

	def p(self, n):
		if n == 0 or n == 1 or n == 2:
			return 1
		else:
			return self.p(n - 2) + self.p(n - 3)


class Solution:

	def padovanSequence(self, n):
		if n in [0, 1, 2]:
			return 1
		else:
			arr = [0] * (n + 1)
			(arr[0], arr[1], arr[2]) = (1, 1, 1)
			for i in range(3, n + 1):
				arr[i] = arr[i - 2] + arr[i - 3]
				arr[i] = arr[i] % (10 ** 9 + 7)
			return arr[-1]


class Solution:

	def padovanSequence(self, n):
		a = [1, 1, 1]
		if n > 2:
			for i in range(3, n):
				k = a[i - 2] + a[i - 3]
				a.append(k)
			return a[n - 2] + a[n - 3]
		else:
			return a[n]


class Solution:

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