Given a triangular pyramid with its vertices marked as O, A, B and C and a number N, the task is to find the number of ways such that a person starting from the origin O initially, reaches back to the origin in N steps. In a single step, a person can go to any of its adjacent vertices.
Example 1:
Input:
N = 1
Output: 0
Explanation: The minimum length of
a cyclic path is 2.
Example 2:
Input:
N = 2
Output: 3
Explanation: The three paths are :
O-A-O, O-B-O, O-C-O
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countPaths() which takes an integer N as input parameter and returns the number of possible paths. Since the answer may be big, return it modulo (10^9+7). 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def countPaths (self, N):

        # code here 

        

Solutions:
import sys
sys.setrecursionlimit(10000)
from functools import lru_cache

class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		ans = 0
		for i in range(2, N + 1):
			if i % 2 == 0:
				ans = 3 * (ans + 1)
			else:
				ans = 3 * (ans - 1)
			ans = ans % (1000000000.0 + 7)
		return int(ans)


class Solution:

	def countPaths(self, N):
		(a, b) = (0, 3)
		if N == 1:
			return 0
		for i in range(N - 2):
			if i & 1:
				b = (b * 3 + 3) % 1000000007
			else:
				b = (b * 3 - 3) % 1000000007
		return b


MODULO = 10 ** 9 + 7

class Solution:

	def countPaths(self, N):
		dp = [0] * max(N + 1, 3)
		dp[0] = 1
		dp[1] = 0
		dp[2] = 3
		pow3 = 3
		for i in range(3, N + 1):
			pow3 *= 3
			pow3 %= MODULO
			dp[i] = (pow3 - dp[i - 1]) % MODULO
		return dp[N]


class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		ans = 0
		for i in range(2, N + 1):
			if i % 2 == 0:
				ans = 3 * (ans + 1)
			else:
				ans = 3 * (ans - 1)
			ans = ans % (1000000000.0 + 7)
		return int(ans)


class Solution:

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


from functools import lru_cache
import sys

class Solution:

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


class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		else:
			result = 0
			for i in range(2, N + 1):
				if i % 2 == 0:
					result = (3 * result + 3) % (10 ** 9 + 7)
				else:
					result = (3 * result - 3) % (10 ** 9 + 7)
			return result % (10 ** 9 + 7)


class Solution:

	def countPaths(self, N):
		mod = 1000000007
		(low, high) = (1, 0)
		(tlow, thigh) = (1, 0)
		for i in range(2, N + 1):
			high = 3 * tlow % mod
			low = (2 * tlow % mod + thigh) % mod
			tlow = low
			thigh = high
		return high


class Solution:

	def countPaths(self, n):
		mod = int(1000000000.0 + 7)
		pre0 = 0
		pre1 = 1
		for i in range(1, n):
			dp1 = 3 * pre1 % mod
			dp2 = (2 * pre1 + pre0) % mod
			pre0 = dp1
			pre1 = dp2
		return pre0


class Solution:

	def countPaths_v1(self, N):
		prevo = 1
		prevA = 0
		prevB = 0
		prevC = 0
		curro = 0
		currA = 0
		currB = 0
		currC = 0
		modv = 10 ** 9 + 7
		for i in range(1, N + 1):
			curro = (prevA + prevB + prevC) % modv
			currA = (prevo + prevB + prevC) % modv
			currB = (prevo + prevA + prevC) % modv
			currC = (prevo + prevA + prevB) % modv
			prevo = curro
			prevA = currA
			prevB = currB
			prevC = currC
		return prevo

	def countPaths(self, N):
		if N == 1:
			return 0
		ans = 0
		for i in range(2, N + 1):
			if i % 2 == 0:
				ans = 3 * (ans + 1)
			else:
				ans = 3 * (ans - 1)
			ans = ans % (1000000000.0 + 7)
		return int(ans)


class Solution:

	def countPaths(self, n):
		ans = 1
		for i in range(1, n + 1):
			if i & 1 == 1:
				ans = (ans * 3 - 3) % (10 ** 9 + 7)
			else:
				ans = (ans * 3 + 3) % (10 ** 9 + 7)
		return ans


class Solution:

	def countPaths(self, N):
		a = 1
		M = 1000000000 + 7
		for i in range(N):
			if i % 2 == 0:
				a = a * 3 - 3
			else:
				a = a * 3 + 3
			a = a % M
		return a


class Solution:

	def countPaths(self, N):
		bigNum = 10 ** 9 + 7
		if N <= 1:
			return 0
		if N == 2:
			return 3
		ans = 0
		prev = 3
		for k in range(2, N):
			if k % 2 == 0:
				ans = 3 * prev - 3
			else:
				ans = 3 * prev + 3
			prev = ans % bigNum
		return prev


class Solution:

	def countPaths(self, N):
		if N < 2:
			return 0
		res = 3
		k = 3
		for temp in range(1, N - 1):
			if temp % 2 == 0:
				res = (res * 3 + k) % (10 ** 9 + 7)
			else:
				res = (res * 3 - k) % (10 ** 9 + 7)
		return res


class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		mod = 10 ** 9 + 7
		(p2, p1) = (0, 1)
		for i in range(2, N):
			(p2, p1) = (p1, (2 * p1 + 3 * p2) % mod)
		ans = 3 * p1 % mod
		return ans


class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		mod = 10 ** 9 + 7
		t1 = 1
		t2 = 0
		for i in range(2, N):
			(t2, t1) = (t1, (2 * t1 + 3 * t2) % mod)
		ans = 3 * t1 % mod
		return ans


class Solution:

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


MOD = 1000000007

class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		res = 0
		for i in range(2, N + 1):
			if i & 1:
				res = (res * 3 - 3) % MOD
			else:
				res = (res * 3 + 3) % MOD
		return res % MOD


class Solution:

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


class Solution:

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


class Solution:

	def countPaths(self, N):
		M = 1000000007
		if N <= 1:
			return 0
		prev0 = 2
		prev1 = 3
		for i in range(3, N + 1):
			temp1 = 3 * prev0 % M
			temp0 = (2 * prev0 + prev1) % M
			prev0 = temp0
			prev1 = temp1
		return prev1


class Solution:

	def countPaths(self, N):
		M = 1000000000.0 + 7
		if N <= 1:
			return 0
		prev0 = 2
		prev1 = 3
		for i in range(3, N + 1):
			temp1 = 3 * prev0 % M
			temp0 = (2 * prev0 + prev1) % M
			prev0 = temp0
			prev1 = temp1
		return int(prev1)


class Solution:

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


class Solution:

	def countPaths(self, n):
		if n < 2:
			return 0
		m = 10 ** 9
		m += 7
		t = 0
		i = 2
		while i <= n:
			t = t * 3 % m
			if i % 2:
				t -= 3
			else:
				t = (t + 3) % m
			i += 1
		return t


class Solution:

	def countPaths(self, N):
		res = (3 ** N + 3 * (-1) ** N) * 250000002 % 1000000007
		return int(res)


class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		(val, curr, mod) = (0, 2, 10 ** 9 + 7)
		while curr <= N:
			if curr % 2 == 0:
				val = (val + 1) * 3 % mod
			else:
				val = (val - 1) * 3 % mod
			curr += 1
		return val


class Solution:

	def countPaths(self, n):
		add = True
		ans = 0
		for i in range(n - 1):
			if add:
				ans = ans * 3 + 3
			else:
				ans = ans * 3 - 3
			add = not add
			ans = ans % 1000000007
		return ans % 1000000007


class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		m = 10 ** 9 + 7
		t1 = 1
		t2 = 0
		for i in range(2, N):
			(t2, t1) = (t1, (2 * t1 + 3 * t2) % m)
		res = 3 * t1 % m
		return res


class Solution:

	def countPaths(self, N):
		if N == 1:
			return 0
		mod = 10 ** 9 + 7
		(prev, current) = (0, 1)
		for i in range(2, N):
			(prev, current) = (current, (2 * current + 3 * prev) % mod)
		return 3 * current % mod


class Solution:

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


class Solution:

	def countPaths(self, N):
		if N < 2:
			return 0
		m = 1000000007
		t = 0
		i = 2
		while i <= N:
			t = t * 3 % m
			if i % 2 != 0:
				t -= 3
			else:
				t = (t + 3) % m
			i += 1
		return t


class Solution:

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