Given the mobile numeric keypad. You can only press buttons that are up, left, right, or down to the current button or the current button itself (like 00,11, etc.). You are not allowed to press the bottom row corner buttons (i.e. * and # ). Given a number N, the task is to find out the number of possible numbers of the given length.
Example 1:
Input: 1
Output: 10
Explanation: Number of possible numbers 
would be 10 (0, 1, 2, 3, ., 9)  
Example 2:
Input: N = 2
Output: 36
Explanation: Possible numbers: 00, 08, 11,
12, 14, 22, 21, 23, 25 and so on.
If we start with 0, valid numbers 
will be 00, 08 (count: 2)
If we start with 1, valid numbers 
will be 11, 12, 14 (count: 3)
If we start with 2, valid numbers 
will be 22, 21, 23,25 (count: 4)
If we start with 3, valid numbers 
will be 33, 32, 36 (count: 3)
If we start with 4, valid numbers 
will be 44,41,45,47 (count: 4)
If we start with 5, valid numbers 
will be 55,54,52,56,58 (count: 5) 
and so on..
Your Task:  
You don't need to read input or print anything. Complete the function getCount() which takes N as input parameter and returns the integer value
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 25

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:

	def getCount(self, N):

		# code here

Solutions:
class Solution:

	def getCount(self, N):
		neigh = [[0, 8], [1, 2, 4], [1, 2, 3, 5], [2, 3, 6], [1, 4, 5, 7], [2, 4, 5, 6, 8], [3, 5, 6, 9], [4, 7, 8], [5, 7, 8, 9, 0], [6, 8, 9]]
		dp = [-1 for j in range(10)]
		ans = [-1 for j in range(10)]
		for i in range(10):
			ans[i] = 1
		for n in range(2, N + 1):
			for k in range(10):
				res = 0
				for i in neigh[k]:
					res += ans[i]
				dp[k] = res
			ans = dp
			dp = [-1 for _ in range(10)]
		return sum(ans)


class Solution:

	def solve(self, i, j, n, arr, dp):
		if n == 1:
			return 1
		if dp[arr[i][j]][n] != -1:
			return dp[arr[i][j]][n]
		(a, b, c, d, e) = (0, 0, 0, 0, 0)
		a = self.solve(i, j, n - 1, arr, dp)
		if i + 1 < 4 and arr[i + 1][j] != -1:
			b = self.solve(i + 1, j, n - 1, arr, dp)
		if i - 1 >= 0 and arr[i - 1][j] != -1:
			c = self.solve(i - 1, j, n - 1, arr, dp)
		if j + 1 < 3 and arr[i][j + 1] != -1:
			d = self.solve(i, j + 1, n - 1, arr, dp)
		if j - 1 >= 0 and arr[i][j - 1] != -1:
			e = self.solve(i, j - 1, n - 1, arr, dp)
		dp[arr[i][j]][n] = a + b + c + d + e
		return dp[arr[i][j]][n]

	def getCount(self, N):
		i = 0
		j = 0
		res = 0
		dp = [[-1 for i in range(N + 1)] for i in range(10)]
		arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		for i in range(4):
			for j in range(3):
				if arr[i][j] != -1:
					res += self.solve(i, j, N, arr, dp)
		return res


class Solution:

	def solve(self, ind, N, data, dp):
		if N == 1:
			return 1
		if dp[N][ind] != -1:
			return dp[N][ind]
		ans = 0
		for e1 in data[ind]:
			ans += self.solve(e1, N - 1, data, dp)
		dp[N][ind] = ans
		return dp[N][ind]

	def getCount(self, N):
		data = {0: [0, 8], 1: [1, 2, 4], 2: [1, 2, 3, 5], 3: [2, 3, 6], 4: [4, 1, 5, 7], 5: [2, 4, 5, 6, 8], 6: [3, 5, 6, 9], 7: [4, 7, 8], 8: [5, 7, 8, 9, 0], 9: [6, 8, 9]}
		dp = [[-1 for i in range(10)] for j in range(N + 1)]
		res = 0
		for i in range(10):
			a = self.solve(i, N, data, dp)
			res += a
		return res


class Solution:

	def getCount(self, N):
		neigh = [[0, 8], [1, 2, 4], [1, 2, 3, 5], [2, 3, 6], [1, 4, 5, 7], [2, 4, 5, 6, 8], [3, 5, 6, 9], [4, 7, 8], [5, 7, 8, 9, 0], [6, 8, 9]]
		dp = [[-1 for j in range(10)] for i in range(N + 1)]

		def foo(dp, n, k):
			if n == 1:
				return 1
			if dp[n][k] != -1:
				return dp[n][k]
			res = 0
			for i in neigh[k]:
				res += foo(dp, n - 1, i)
			dp[n][k] = res
			return dp[n][k]
		res = 0
		for i in range(10):
			res += foo(dp, N, i)
		return res


class Solution:

	def getCount(self, N):
		stateMap = [[0] * 10 for _ in range(N)]
		stateMap[0] = [1] * 10
		for i in range(1, N):
			stateMap[i][0] = stateMap[i - 1][0] + stateMap[i - 1][8]
			stateMap[i][1] = stateMap[i - 1][1] + stateMap[i - 1][2] + stateMap[i - 1][4]
			stateMap[i][2] = stateMap[i - 1][1] + stateMap[i - 1][2] + stateMap[i - 1][3] + stateMap[i - 1][5]
			stateMap[i][3] = stateMap[i - 1][2] + stateMap[i - 1][3] + stateMap[i - 1][6]
			stateMap[i][4] = stateMap[i - 1][1] + stateMap[i - 1][7] + stateMap[i - 1][4] + stateMap[i - 1][5]
			stateMap[i][5] = stateMap[i - 1][2] + stateMap[i - 1][4] + stateMap[i - 1][6] + stateMap[i - 1][5] + stateMap[i - 1][8]
			stateMap[i][6] = stateMap[i - 1][3] + stateMap[i - 1][6] + stateMap[i - 1][9] + stateMap[i - 1][5]
			stateMap[i][7] = stateMap[i - 1][4] + stateMap[i - 1][7] + stateMap[i - 1][8]
			stateMap[i][8] = stateMap[i - 1][7] + stateMap[i - 1][9] + stateMap[i - 1][8] + stateMap[i - 1][5] + stateMap[i - 1][0]
			stateMap[i][9] = stateMap[i - 1][8] + stateMap[i - 1][9] + stateMap[i - 1][6]
		return sum(stateMap[-1])


import sys

class Solution:

	def getCount(self, n):
		mp = dict()
		for i in range(0, 10):
			if i == 0:
				mp[i] = [0, 8]
			elif i == 1:
				mp[i] = [1, 2, 4]
			elif i == 2:
				mp[i] = [2, 1, 5, 3]
			elif i == 3:
				mp[i] = [3, 2, 6]
			elif i == 4:
				mp[i] = [4, 1, 7, 5]
			elif i == 5:
				mp[i] = [5, 2, 4, 6, 8]
			elif i == 6:
				mp[i] = [6, 3, 5, 9]
			elif i == 7:
				mp[i] = [7, 4, 8]
			elif i == 8:
				mp[i] = [8, 5, 7, 9, 0]
			elif i == 9:
				mp[i] = [9, 6, 8]
		dp = [[0] * 10 for i in range(n + 1)]
		for i in range(1, n + 1):
			if i == 1:
				for j in range(0, 10):
					dp[i][j] = 1
			for j in range(0, 10):
				for x in mp[j]:
					dp[i][j] += dp[i - 1][x]
		res = 0
		for i in range(10):
			res += dp[n][i]
		return res


class Solution:

	def getCount(self, N):
		new = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
		if N == 1:
			return 10
		news = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
		for i in range(N - 1):
			news[0] = new[0] + new[8]
			news[1] = new[1] + new[2] + new[4]
			news[2] = new[2] + new[1] + new[3] + new[5]
			news[3] = new[3] + new[2] + new[6]
			news[4] = new[1] + new[4] + new[5] + new[7]
			news[5] = new[5] + new[4] + new[2] + new[6] + new[8]
			news[6] = new[3] + new[6] + new[9] + new[5]
			news[7] = new[4] + new[7] + new[8]
			news[8] = new[5] + new[7] + new[8] + new[9] + new[0]
			news[9] = new[6] + new[9] + new[8]
			new = news[:]
		s = 0
		for i in range(10):
			s = s + new[i]
		return s


class Solution:

	def getCount(self, N):
		m = 4
		n = 3
		grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [0, 0, 0]]
		vis = set()
		total = 0
		dp = {}

		def f(r, c, digit):
			if (r, c, digit) in dp:
				return dp[r, c, digit]
			if r < 0 or c < 0 or r == m or (c == n) or ([r, c] == [3, 0]) or ([r, c] == [3, 2]):
				return 0
			if digit == N:
				return 1
			temp = 0
			temp += f(r, c, digit + 1)
			temp += f(r + 1, c, digit + 1)
			temp += f(r, c - 1, digit + 1)
			temp += f(r, c + 1, digit + 1)
			temp += f(r - 1, c, digit + 1)
			dp[r, c, digit] = temp
			return temp
		total = 0
		for i in range(m):
			for j in range(n):
				if [i, j] != [3, 0] and [i, j] != [3, 2] and ((i, j) not in vis):
					vis.add((i, j))
					total += f(i, j, 1)
		return total


import numpy as np

class Solution:

	def getCount(self, N):
		matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9], ['*', 0, '*']]
		if N == 0:
			return 0
		if N == 1:
			return 10
		count = [[0 for i in range(N + 1)] for j in range(10)]
		for i in range(10):
			count[i][0] = 0
			count[i][1] = 1
		dx = [0, 1, -1, 0, 0]
		dy = [0, 0, 0, 1, -1]
		for k in range(2, N + 1):
			for i in range(4):
				for j in range(3):
					if matrix[i][j] != '*':
						for move in range(5):
							ro = i + dx[move]
							co = j + dy[move]
							if 0 <= ro <= 3 and 0 <= co <= 2 and (matrix[ro][co] != '*'):
								count[matrix[i][j]][k] += count[matrix[ro][co]][k - 1]
		total = 0
		for i in range(10):
			total += count[i][N]
		return total


class Solution:

	def getCount(self, n):
		a = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		if n == 1:
			return 10

		def manu(a, i, j, n, dp):
			if a[i][j] == -1:
				return 0
			if n == 0:
				return 1
			if dp[i][j][n] != -1:
				return dp[i][j][n]
			(up, down, left, right, auto) = (0, 0, 0, 0, 0)
			if i - 1 >= 0:
				up = manu(a, i - 1, j, n - 1, dp)
			if i + 1 <= 3:
				down = manu(a, i + 1, j, n - 1, dp)
			if j - 1 >= 0:
				left = manu(a, i, j - 1, n - 1, dp)
			if j + 1 <= 2:
				right = manu(a, i, j + 1, n - 1, dp)
			sel = manu(a, i, j, n - 1, dp)
			dp[i][j][n] = up + down + sel + left + right
			return dp[i][j][n]
		maxi = 0
		for i in range(4):
			for j in range(3):
				dp = [[[-1 for i in range(n)] for i in range(3)] for i in range(4)]
				maxi += manu(a, i, j, n - 1, dp)
		return maxi


class Solution:

	def getCount(self, N):
		dic = {1: [2, 4], 2: [1, 3, 5], 3: [2, 6], 4: [1, 5, 7], 5: [2, 4, 6, 8], 6: [3, 5, 9], 7: [4, 8], 8: [5, 7, 9, 0], 9: [6, 8], 0: [8]}
		dp = [[0 for i in range(10)] for i in range(N)]
		for i in range(10):
			dp[0][i] = 1
		for i in range(1, N):
			for num in range(10):
				dp[i][num] = dp[i - 1][num]
				for n in dic[num]:
					dp[i][num] += dp[i - 1][n]
		return sum(dp[-1])


class Solution:

	def getCount(self, n):
		if n == 1:
			return 10
		d = {0: [0, 8], 1: [1, 2, 4], 2: [2, 1, 3, 5], 3: [3, 2, 6], 4: [4, 1, 5, 7], 5: [5, 2, 4, 6, 8], 6: [6, 3, 5, 9], 7: [7, 4, 8], 8: [8, 5, 7, 9, 0], 9: [9, 6, 8]}
		cur = [0] * 10
		prev = [1] * 10
		for i in range(1, n):
			for j in range(10):
				cur[j] = 0
				for k in d[j]:
					cur[j] += prev[k]
			prev = cur.copy()
		return sum(cur)


class Solution:

	def getCount(self, N):
		mat = [['1', '2', '3'], ['4', '5', '6'], ['7', '8', '9'], ['*', '0', '#']]
		d = dict()

		def dfs(mat, N, i, j):
			if i == len(mat) or j == len(mat[0]) or i < 0 or (j < 0):
				return 0
			if mat[i][j] == '*' or mat[i][j] == '#':
				return 0
			if N == 1:
				return 1
			if d.get((i, j, N)) != None:
				return d[i, j, N]
			d[i, j, N] = dfs(mat, N - 1, i, j) + dfs(mat, N - 1, i + 1, j) + dfs(mat, N - 1, i, j + 1) + dfs(mat, N - 1, i - 1, j) + dfs(mat, N - 1, i, j - 1)
			return d[i, j, N]
		count = 0
		if N == 1:
			return 10
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j] == '*' or mat[i][j] == '#':
					continue
				count = count + dfs(mat, N, i, j)
		return count


class Solution:

	def getCount(self, N):
		dp = [None] + [1] * 11
		nextdp = [None] + [0] * 11
		answer = 10
		for i1 in range(N - 1):
			answer = 0
			for i2 in range(1, 12):
				if i2 == 10:
					continue
				d1 = i2 - 3
				d2 = i2 - 1
				d3 = i2 + 3
				d4 = i2 + 1
				save = dp[i2]
				if 0 < d1 < 12 and d1 != 10:
					save += dp[d1]
				if 0 < d2 < 12 and d2 != 10 and ((i2 - 1) % 3 != 0):
					save += dp[d2]
				if 0 < d3 < 12 and d3 != 10:
					save += dp[d3]
				if 0 < d4 < 12 and d4 != 10 and (i2 % 3 != 0):
					save += dp[d4]
				nextdp[i2] = save
				answer += save
			dp = nextdp
			nextdp = [None] + [0] * 12
		return answer


class Solution:

	def getCount(self, N):
		dp = [[0 for i in range(10)] for j in range(N)]
		lis = [[0, 8], [1, 2, 4], [1, 2, 3, 5], [3, 2, 6], [4, 1, 5, 7], [5, 2, 4, 6, 8], [6, 3, 5, 9], [7, 8, 4], [8, 0, 7, 9, 5], [9, 8, 6]]
		for i in range(10):
			dp[0][i] = 1
		for i in range(1, N):
			for j in range(10):
				for k in lis[j]:
					dp[i][j] += dp[i - 1][k]
		return sum(dp[N - 1])


class Solution:

	def getCount(self, N):
		table = [[1, 2, 3], [4, 5, 6], [7, 8, 9], ['*', 0, '#']]
		(count, hmap) = (0, {})

		def mobile(table, i, j, N):
			if i < 0 or j < 0 or i >= 4 or (j >= 3) or (table[i][j] == '#') or (table[i][j] == '*'):
				return 0
			if N == 1:
				return 1
			if (i, j, N) not in hmap:
				hmap[i, j, N] = mobile(table, i + 1, j, N - 1) + mobile(table, i, j, N - 1) + mobile(table, i - 1, j, N - 1) + mobile(table, i, j + 1, N - 1) + mobile(table, i, j - 1, N - 1)
			return hmap[i, j, N]
		for i in range(3):
			for j in range(3):
				count += mobile(table, i, j, N)
		count += mobile(table, 3, 1, N)
		return count


class Solution:

	def getCount(self, N):

		def recursion(n, i, j):
			if dp[mat[i][j]][n] != -1:
				return dp[mat[i][j]][n]
			if n == 1:
				return 1
			a = recursion(n - 1, i, j)
			b = 0
			c = 0
			d = 0
			e = 0
			if i - 1 >= 0 and mat[i - 1][j] != -1:
				b = recursion(n - 1, i - 1, j)
			if j - 1 >= 0 and mat[i][j - 1] != -1:
				c = recursion(n - 1, i, j - 1)
			if i + 1 < 4 and mat[i + 1][j] != -1:
				d = recursion(n - 1, i + 1, j)
			if j + 1 < 3 and mat[i][j + 1] != -1:
				e = recursion(n - 1, i, j + 1)
			dp[mat[i][j]][n] = a + b + c + d + e
			return dp[mat[i][j]][n]
		dp = [[-1 for i in range(N + 1)] for i in range(10)]
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		ans = 0
		for i in range(4):
			for j in range(3):
				if mat[i][j] != -1:
					ans += recursion(N, i, j)
		return ans


class Solution:

	def getCount(self, N):
		key_pad = [[0, 8], [1, 4, 2], [2, 1, 3, 5], [3, 2, 6], [4, 1, 5, 7], [5, 2, 4, 8, 6], [6, 3, 5, 9], [7, 4, 8], [8, 5, 7, 0, 9], [9, 6, 8]]
		dp = [[None for j in range(10)] for i in range(2)]
		ans = 0
		for n in range(1, N + 1):
			for i in range(10):
				if n == 1:
					dp[1][i] = 1
				else:
					dp[1][i] = 0
					for next_i in key_pad[i]:
						dp[1][i] += dp[0][next_i]
				if n == N:
					ans += dp[1][i]
			(dp[0], dp[1]) = (dp[1], dp[0])
		return ans


class Solution:

	def getCount(self, N):
		moves = [[0, 8], [1, 2, 4], [2, 1, 3, 5], [3, 2, 6], [4, 1, 5, 7], [5, 2, 8, 6, 4], [6, 3, 5, 9], [7, 4, 8], [8, 5, 0, 9, 7], [9, 6, 8]]
		result = [1] * 10
		hops = 0
		nextResult = []
		while hops < N - 1:
			nextResult = [0] * len(result)
			for idx in range(len(moves)):
				for step in moves[idx]:
					nextResult[idx] += result[step]
			result = nextResult[:]
			hops += 1
		return sum(result)


def sol(n):
	dp = [[1 for i in range(n + 1)] for j in range(10)]
	for i in range(2, n + 1):
		dp[0][i] = dp[0][i - 1] + dp[8][i - 1]
		dp[1][i] = dp[1][i - 1] + dp[2][i - 1] + dp[4][i - 1]
		dp[2][i] = dp[1][i - 1] + dp[2][i - 1] + dp[3][i - 1] + dp[5][i - 1]
		dp[3][i] = dp[2][i - 1] + dp[3][i - 1] + dp[6][i - 1]
		dp[4][i] = dp[1][i - 1] + dp[4][i - 1] + dp[7][i - 1] + dp[5][i - 1]
		dp[5][i] = dp[2][i - 1] + dp[4][i - 1] + dp[6][i - 1] + dp[5][i - 1] + dp[8][i - 1]
		dp[6][i] = dp[6][i - 1] + dp[9][i - 1] + dp[3][i - 1] + dp[5][i - 1]
		dp[7][i] = dp[4][i - 1] + dp[7][i - 1] + dp[8][i - 1]
		dp[8][i] = dp[7][i - 1] + dp[9][i - 1] + dp[0][i - 1] + dp[5][i - 1] + dp[8][i - 1]
		dp[9][i] = dp[6][i - 1] + dp[9][i - 1] + dp[8][i - 1]
	ans = 0
	for j in range(10):
		ans += dp[j][n]
	return ans

class Solution:

	def getCount(self, N):
		return sol(N)


class Solution:

	def getCount(self, N):

		def solve(grid, i, j, steps, dp):
			if i >= len(grid) or j >= len(grid[0]) or j < 0 or (i < 0) or (grid[i][j] == -1):
				return 0
			if steps == 1:
				return 1
			if (i, j, steps) in dp:
				return dp[i, j, steps]
			a = solve(grid, i + 1, j, steps - 1, dp)
			b = solve(grid, i - 1, j, steps - 1, dp)
			c = solve(grid, i, j + 1, steps - 1, dp)
			d = solve(grid, i, j - 1, steps - 1, dp)
			e = solve(grid, i, j, steps - 1, dp)
			dp[i, j, steps] = a + b + c + d + e
			return dp[i, j, steps]
		grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		ans = 0
		dp = {}
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != -1:
					ans += solve(grid, i, j, N, dp)
		return ans


class Solution:

	def getCount(self, N):
		if N == 1:
			return 10
		d = {0: [0, 8], 1: [1, 2, 4], 2: [2, 1, 3, 5], 3: [3, 2, 6], 4: [4, 1, 5, 7], 5: [5, 2, 4, 6, 8], 6: [6, 3, 5, 9], 7: [7, 4, 8], 8: [8, 5, 7, 9, 0], 9: [9, 6, 8]}
		prev = [1] * 10
		curr = [0] * 10
		for ppp in range(1, N):
			for i in range(10):
				curr[i] = 0
				for j in d[i]:
					curr[i] += prev[j]
			prev = curr.copy()
		return sum(curr)


class Solution:

	def getCount(self, N):
		ans = 10
		arr1 = [1] * 10
		arr2 = [0] * 10
		a = [[0, 8], [1, 2, 4], [1, 2, 3, 5], [2, 3, 6], [1, 4, 5, 7], [2, 4, 5, 6, 8], [3, 5, 6, 9], [4, 7, 8], [5, 7, 8, 9, 0], [6, 8, 9]]
		for i in range(1, N):
			for j in range(10):
				for k in a[j]:
					arr2[j] += arr1[k]
			ans = sum(arr2)
			arr1 = arr2
			arr2 = [0] * 10
		return ans


class Solution:

	def getCount(self, N):
		memo = {}
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]

		def solve(i, j, n):
			key = (i, j, n)
			if n == 1:
				memo[key] = 1
			if key in memo:
				return memo[key]
			a = solve(i, j, n - 1)
			b = 0
			c = 0
			d = 0
			e = 0
			if j - 1 >= 0 and mat[i][j - 1] != -1:
				b = solve(i, j - 1, n - 1)
			if j + 1 < 3 and mat[i][j + 1] != -1:
				c = solve(i, j + 1, n - 1)
			if i + 1 < 4 and mat[i + 1][j] != -1:
				d = solve(i + 1, j, n - 1)
			if i - 1 >= 0 and mat[i - 1][j] != -1:
				e = solve(i - 1, j, n - 1)
			memo[key] = a + b + c + d + e
			return memo[key]
		ans = 0
		for i in range(4):
			for j in range(3):
				if mat[i][j] != -1:
					ans += solve(i, j, N)
		return ans


class Solution:

	def getCount(self, N):
		t = [[0 for i in range(10)] for j in range(N + 2)]
		data = [[0, 8], [1, 2, 4], [1, 2, 3, 5], [2, 3, 6], [1, 4, 5, 7], [2, 4, 5, 6, 8], [3, 5, 6, 9], [4, 7, 8], [5, 7, 8, 9, 0], [6, 8, 9]]
		for i in range(1, N + 1):
			for j in range(0, 10):
				if i == 1:
					t[i][j] = 1
				else:
					for prev in data[j]:
						t[i][j] += t[i - 1][prev]
		sum = 0
		for j in range(0, 10):
			sum += t[N][j]
		return sum


class Solution:

	def getCount(self, N):
		dic = [1] * 10
		if N == 1:
			return sum(dic)
		count = {0: [0, 8], 1: [1, 2, 4], 2: [1, 2, 3, 5], 3: [2, 3, 6], 4: [1, 4, 5, 7], 5: [2, 4, 5, 6, 8], 6: [3, 5, 6, 9], 7: [4, 7, 8], 8: [0, 5, 7, 8, 9], 9: [6, 8, 9]}
		dummy = dic.copy()
		n = 1
		while n < N:
			for i in range(10):
				res = 0
				for ele in count[i]:
					res += dummy[ele]
				dic[i] = res
			dummy = dic.copy()
			n += 1
		return sum(dic)


class Solution:

	def getCount(self, n):
		if n == 1:
			return 10
		else:
			keymap = {0: [8], 1: [2, 4], 2: [1, 3, 5], 3: [2, 6], 4: [1, 5, 7], 5: [2, 4, 6, 8], 6: [3, 5, 9], 7: [4, 8], 8: [5, 7, 9, 0], 9: [8, 6]}
			dp = [[1] * 10 for i in range(n + 1)]
			for i in range(2, n + 1):
				for j in range(10):
					dp[i][j] = dp[i - 1][j]
					for k in keymap[j]:
						dp[i][j] += dp[i - 1][k]
			return sum(dp[n])


class Solution:

	def getCount(self, n):
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		rows = len(mat)
		cols = len(mat[0])
		dp = [[-1] * (n + 1) for i in range(10)]
		ans = 0

		def solve(i, j, n):
			if n == 1:
				return 1
			if dp[mat[i][j]][n] != -1:
				return dp[mat[i][j]][n]
			a = solve(i, j, n - 1)
			(b, c, d, e) = (0, 0, 0, 0)
			if j - 1 in range(cols) and mat[i][j - 1] != -1:
				b = solve(i, j - 1, n - 1)
			if j + 1 in range(cols) and mat[i][j + 1] != -1:
				c = solve(i, j + 1, n - 1)
			if i - 1 in range(rows) and mat[i - 1][j] != -1:
				d = solve(i - 1, j, n - 1)
			if i + 1 in range(rows) and mat[i + 1][j] != -1:
				e = solve(i + 1, j, n - 1)
			dp[mat[i][j]][n] = a + b + c + d + e
			return dp[mat[i][j]][n]
		for i in range(rows):
			for j in range(cols):
				if mat[i][j] != -1:
					ans += solve(i, j, n)
		return ans


class Solution:

	def getCount(self, n):
		if n == 1:
			return 10
		d = {}
		for i in range(10):
			d[i] = 1
		l = [1, 2, 3, 2, 3, 4, 3, 2, 4, 2]
		i = 2
		r = 10
		while i < n + 1:
			for j in range(10):
				r += d[j] * l[j]
			d1 = d.copy()
			d[0] += d1[8]
			d[1] += d1[4] + d1[2]
			d[2] += d1[1] + d1[3] + d1[5]
			d[3] += d1[6] + d1[2]
			d[4] += d1[1] + d1[5] + d1[7]
			d[5] += d1[2] + d1[4] + d1[6] + d1[8]
			d[6] += d1[9] + d1[3] + d1[5]
			d[7] += d1[4] + d1[8]
			d[8] += d1[0] + d1[5] + d1[9] + d1[7]
			d[9] += d1[8] + d1[6]
			i += 1
		return r


class Solution:

	def getCount(self, N):
		if N <= 0:
			return 0
		if N == 1:
			return 10
		keypad = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [None, 0, None]]
		rows = len(keypad)
		cols = len(keypad[0])
		directions = [[0, 0], [0, 1], [0, -1], [-1, 0], [1, 0]]
		dp = [[[None for k in range(N + 1)] for j in range(cols + 1)] for i in range(rows + 1)]

		def f(r, c, n):
			if n == 1:
				return 1
			if dp[r][c][n]:
				return dp[r][c][n]
			count = 0
			for (dr, dc) in directions:
				if r + dr in range(rows) and c + dc in range(cols) and (keypad[r + dr][c + dc] is not None):
					count += f(r + dr, c + dc, n - 1)
			dp[r][c][n] = count
			return dp[r][c][n]
		total = 0
		for r in range(rows):
			for c in range(cols):
				if keypad[r][c] is not None:
					total += f(r, c, N)
		return total


class Solution:

	def getCount(self, n):
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		r = len(mat)
		c = len(mat[0])
		dp = [[-1] * (n + 1) for i in range(10)]
		ans = 0

		def solve(i, j, n):
			if n == 1:
				return 1
			if dp[mat[i][j]][n] != -1:
				return dp[mat[i][j]][n]
			curr = solve(i, j, n - 1)
			(up, left, right, down) = (0, 0, 0, 0)
			if i - 1 in range(r) and mat[i - 1][j] != -1:
				up = solve(i - 1, j, n - 1)
			if j - 1 in range(c) and mat[i][j - 1] != -1:
				left = solve(i, j - 1, n - 1)
			if j + 1 in range(c) and mat[i][j + 1] != -1:
				right = solve(i, j + 1, n - 1)
			if i + 1 in range(r) and mat[i + 1][j] != -1:
				down = solve(i + 1, j, n - 1)
			dp[mat[i][j]][n] = curr + up + left + right + down
			return dp[mat[i][j]][n]
		for i in range(r):
			for j in range(c):
				if mat[i][j] != -1:
					ans += solve(i, j, n)
		return ans


class Solution:

	def getCountHelper(self, i, j, mat, moves, targetLen, memory):
		if i < 0 or i >= len(mat) or j < 0 or (j >= len(mat[0])):
			return 0
		if mat[i][j] == '*' or mat[i][j] == '#' or targetLen <= 0:
			return 0
		if targetLen == 1:
			return 1
		num = int(mat[i][j])
		if memory[num][targetLen] != -1:
			return memory[num][targetLen]
		ans = 0
		ans += self.getCountHelper(i, j, mat, moves, targetLen - 1, memory)
		for move in moves:
			curri = i + move[0]
			currj = j + move[1]
			ans += self.getCountHelper(curri, currj, mat, moves, targetLen - 1, memory)
		memory[num][targetLen] = ans
		return memory[num][targetLen]

	def getCount(self, N):
		ans = 0
		mat = [['1', '2', '3'], ['4', '5', '6'], ['7', '8', '9'], ['*', '0', '#']]
		moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		memory = []
		for x in range(10):
			currRow = []
			for y in range(N + 1):
				currRow.append(-1)
			memory.append(currRow)
		ans = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				ans += self.getCountHelper(i, j, mat, moves, N, memory)
		return ans


class Solution:

	def getCount(self, N):
		if N == 1:
			return 10
		neighbours = {0: [0, 8], 1: [1, 2, 4], 2: [1, 2, 3, 5], 3: [2, 3, 6], 4: [1, 4, 5, 7], 5: [2, 4, 5, 6, 8], 6: [3, 5, 6, 9], 7: [4, 7, 8], 8: [0, 5, 7, 8, 9], 9: [6, 8, 9]}
		cur = [1] * 10
		new = [0] * 10
		for i in range(2, N + 1):
			for j in range(10):
				if i % 2 == 0:
					new[j] = 0
					for k in neighbours[j]:
						new[j] += cur[k]
				else:
					cur[j] = 0
					for k in neighbours[j]:
						cur[j] += new[k]
		if N % 2 == 0:
			return sum(new)
		else:
			return sum(cur)


class Solution:

	def helper(self, i, j, n, mob, dp):
		if n == 1:
			return 1
		if dp[mob[i][j]][n] != -1:
			return dp[mob[i][j]][n]
		own = self.helper(i, j, n - 1, mob, dp)
		left = right = up = down = 0
		if i + 1 < 4 and mob[i + 1][j] != -1:
			up = self.helper(i + 1, j, n - 1, mob, dp)
		if i - 1 >= 0 and mob[i - 1][j] != -1:
			down = self.helper(i - 1, j, n - 1, mob, dp)
		if j - 1 >= 0 and mob[i][j - 1] != -1:
			left = self.helper(i, j - 1, n - 1, mob, dp)
		if j + 1 < 3 and mob[i][j + 1] != -1:
			right = self.helper(i, j + 1, n - 1, mob, dp)
		dp[mob[i][j]][n] = own + left + right + up + down
		return dp[mob[i][j]][n]

	def mobile_key(self, i, j, row, col, mob, ans_str, res, n):
		if i < 0 or j < 0 or i >= row or (j >= col) or (mob[i][j] == -1):
			return
		if len(ans_str) == n:
			res.add(tuple(ans_str))
			return
		self.mobile_key(i, j, row, col, mob, ans_str + [mob[i][j]], res, n)
		self.mobile_key(i - 1, j, row, col, mob, ans_str + [mob[i][j]], res, n)
		self.mobile_key(i + 1, j, row, col, mob, ans_str + [mob[i][j]], res, n)
		self.mobile_key(i, j - 1, row, col, mob, ans_str + [mob[i][j]], res, n)
		self.mobile_key(i, j + 1, row, col, mob, ans_str + [mob[i][j]], res, n)

	def getCount(self, N):
		mob = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		row = len(mob)
		col = len(mob[0])
		res = set()
		dp = [[-1] * (N + 1) for i in range(10)]
		ans = 0
		for i in range(4):
			for j in range(3):
				if mob[i][j] != -1:
					ans += self.helper(i, j, N, mob, dp)
		return ans


class Solution:

	def getCount(self, N):
		mat = [[0 for _ in range(N + 1)] for _ in range(10)]
		for j in range(10):
			mat[j][1] = 1
		h = [[0, 8], [1, 2, 4], [2, 1, 3, 5], [3, 2, 6], [4, 1, 5, 7], [5, 2, 4, 6, 8], [6, 3, 5, 9], [7, 4, 8], [8, 5, 7, 9, 0], [9, 6, 8]]
		for i in range(2, N + 1):
			for j in range(10):
				for k in h[j]:
					mat[j][i] += mat[k][i - 1]
		res = 0
		for j in range(10):
			res += mat[j][N]
		return res


def f(adj, n, last, dp):
	if n == 1:
		return 1
	if dp[n][last] != -1:
		return dp[n][last]
	ans = 0
	ans += f(adj, n - 1, last, dp)
	for i in adj[last]:
		ans += f(adj, n - 1, i, dp)
	dp[n][last] = ans
	return ans

class Solution:

	def getCount(self, N):
		adj = [[8], [2, 4], [1, 3, 5], [2, 6], [1, 5, 7], [2, 4, 6, 8], [3, 5, 9], [4, 8], [0, 5, 7, 9], [6, 8]]
		ans = 0
		dp = [[-1 for i in range(10)] for i in range(N + 1)]
		for i in range(10):
			ans += f(adj, N, i, dp)
		return ans


class Solution:

	def count(self, i, j, N, mat, dp):
		if i < 0 or i >= 4 or j < 0 or (j >= 3):
			return 0
		if mat[i][j] == -1:
			return 0
		if N == 1:
			return 1
		if dp[mat[i][j]][N] != -1:
			return dp[mat[i][j]][N]
		dxy = [[0, 0], [0, 1], [0, -1], [1, 0], [-1, 0]]
		count = 0
		for (dx, dy) in dxy:
			new_i = i + dx
			new_j = j + dy
			count += self.count(new_i, new_j, N - 1, mat, dp)
		dp[mat[i][j]][N] = count
		return count

	def getCount(self, N):
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		dp = [[-1 for _ in range(N + 1)] for _ in range(10)]
		count = 0
		for i in range(4):
			for j in range(3):
				count += self.count(i, j, N, mat, dp)
		return count


class Solution:

	def getCount(self, N):
		a = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		r = [0, 0, 0, 1, -1]
		c = [0, -1, 1, 0, 0]
		(nr, nc) = (len(a), len(a[0]))
		dp = [[-1 for _ in range(26)] for _ in range(10)]

		def solve(i, j, n):
			if n == 1:
				return 1
			if dp[a[i][j]][n] != -1:
				return dp[a[i][j]][n]
			res = 0
			for k in range(len(r)):
				(newr, newc) = (i + r[k], j + c[k])
				if 0 <= newr < nr and 0 <= newc < nc and (a[newr][newc] != -1):
					res += solve(newr, newc, n - 1)
			dp[a[i][j]][n] = res
			return dp[a[i][j]][n]
		ans = 0
		for i in range(nr):
			for j in range(nc):
				if a[i][j] != -1:
					ans += solve(i, j, N)
		return ans


class Solution:

	def solve(self, i, j, k, N, arr, ans, lst=[]):
		if k == N:
			if lst not in ans:
				ans.append(lst[:])
			return
		if i < 0 or j < 0 or i >= len(arr) or (j >= len(arr[0])) or (arr[i][j] == -1):
			return
		lst.append(arr[i][j])
		self.solve(i, j, k + 1, N, arr, ans, lst)
		self.solve(i + 1, j, k + 1, N, arr, ans, lst)
		self.solve(i - 1, j, k + 1, N, arr, ans, lst)
		self.solve(i, j + 1, k + 1, N, arr, ans, lst)
		self.solve(i, j - 1, k + 1, N, arr, ans, lst)
		lst.pop()

	def getCount(self, N):
		dp = [1 for i in range(10)]
		prevdp = [1 for i in range(10)]
		for i in range(2, N + 1):
			dp[0] = prevdp[0] + prevdp[8]
			dp[1] = prevdp[1] + prevdp[2] + prevdp[4]
			dp[2] = prevdp[1] + prevdp[2] + prevdp[3] + prevdp[5]
			dp[3] = prevdp[2] + prevdp[3] + prevdp[6]
			dp[4] = prevdp[1] + prevdp[4] + prevdp[5] + prevdp[7]
			dp[5] = prevdp[2] + prevdp[4] + prevdp[5] + prevdp[6] + prevdp[8]
			dp[6] = prevdp[3] + prevdp[5] + prevdp[6] + prevdp[9]
			dp[7] = prevdp[4] + prevdp[7] + prevdp[8]
			dp[8] = prevdp[5] + prevdp[7] + prevdp[8] + prevdp[9] + prevdp[0]
			dp[9] = prevdp[6] + prevdp[8] + prevdp[9]
			for j in range(10):
				prevdp[j] = dp[j]
		ans = 0
		for i in range(10):
			ans += dp[i]
		return ans


class Solution:

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

	def getCount(self, N):

		def f(temp, i, j, n):
			if n <= 0:
				return 0
			if n == 1:
				return 1
			if (i, j, n) in self.d.keys():
				return self.d[i, j, n]
			cr = 0
			for (r, c) in ((1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)):
				r += i
				c += j
				if r >= 0 and c >= 0 and (r < len(temp)) and (c < len(temp[0])) and (temp[r][c] != '*') and (temp[r][c] != '#'):
					cr += f(temp, r, c, n - 1)
			self.d[i, j, n] = cr
			return cr
		temp = [[1, 2, 3], [4, 5, 6], [7, 8, 9], ['*', 0, '#']]
		res = 0
		for i in range(len(temp)):
			for j in range(len(temp[0])):
				if temp[i][j] != '*' and temp[i][j] != '#':
					res += f(temp, i, j, N)
		return res


class Solution:

	def getCount(self, N):
		diction = {0: [0, 8], 1: [1, 2, 4], 2: [2, 1, 3, 5], 3: [3, 2, 6], 4: [4, 1, 5, 7], 5: [5, 4, 2, 6, 8], 6: [6, 3, 5, 9], 7: [7, 8, 4], 8: [8, 0, 9, 7, 5], 9: [9, 6, 8]}
		prev_list = [1] * 10
		new_list = [1] * 10
		for i in range(1, N):
			for j in range(10):
				lis = diction[j]
				sums = 0
				for k in lis:
					sums = prev_list[k] + sums
				new_list[j] = sums
			prev_list = new_list.copy()
		return sum(new_list)


class Solution:

	def mobile(self, i, j, n, arr, dp):
		if n == 1:
			return 1
		if dp[arr[i][j]][n] != -1:
			return dp[arr[i][j]][n]
		a = self.mobile(i, j, n - 1, arr, dp)
		(b, c, d, e) = (0, 0, 0, 0)
		if i - 1 >= 0 and arr[i - 1][j] != -1:
			b = self.mobile(i - 1, j, n - 1, arr, dp)
		if i + 1 < 4 and arr[i + 1][j] != -1:
			c = self.mobile(i + 1, j, n - 1, arr, dp)
		if j - 1 >= 0 and arr[i][j - 1] != -1:
			d = self.mobile(i, j - 1, n - 1, arr, dp)
		if j + 1 < 3 and arr[i][j + 1] != -1:
			e = self.mobile(i, j + 1, n - 1, arr, dp)
		dp[arr[i][j]][n] = a + b + c + d + e
		return dp[arr[i][j]][n]

	def getCount(self, N):
		arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		dp = [[-1 for j in range(N + 1)] for i in range(11)]
		ans = 0
		for i in range(4):
			for j in range(3):
				if arr[i][j] != -1:
					ans += self.mobile(i, j, N, arr, dp)
		return ans


class Solution:

	def solve(self, i, j, n):
		if n == 1:
			return 1
		if self.dp[self.keypad[i][j]][n] != -1:
			return self.dp[self.keypad[i][j]][n]
		a = self.solve(i, j, n - 1)
		if j - 1 >= 0 and self.keypad[i][j - 1] != -1:
			a += self.solve(i, j - 1, n - 1)
		if j + 1 < 3 and self.keypad[i][j + 1] != -1:
			a += self.solve(i, j + 1, n - 1)
		if i - 1 >= 0 and self.keypad[i - 1][j] != -1:
			a += self.solve(i - 1, j, n - 1)
		if i + 1 < 4 and self.keypad[i + 1][j] != -1:
			a += self.solve(i + 1, j, n - 1)
		self.dp[self.keypad[i][j]][n] = a
		return a

	def getCount(self, n):
		self.keypad = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		self.dp = [[-1 for _ in range(n + 1)] for _ in range(10)]
		ans = 0
		for i in range(4):
			for j in range(3):
				if self.keypad[i][j] != -1:
					ans += self.solve(i, j, n)
		return ans


class Solution:

	def getCount(self, n):
		adj = {}
		adj[0] = [0, 8]
		adj[1] = [1, 2, 4]
		adj[2] = [1, 2, 3, 5]
		adj[3] = [2, 6, 3]
		adj[4] = [1, 5, 7, 4]
		adj[5] = [2, 4, 6, 8, 5]
		adj[6] = [3, 5, 9, 6]
		adj[7] = [4, 8, 7]
		adj[8] = [5, 7, 9, 8, 0]
		adj[9] = [6, 8, 9]
		dp = [[0 for _ in range(10)] for _ in range(n + 1)]
		dp[1] = [1] * 10
		for i in range(2, n + 1):
			for j in range(10):
				for x in adj[j]:
					dp[i][j] += dp[i - 1][x]
		return sum(dp[n])


class Solution:

	def getCount(self, N):
		grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		d = {1: (0, 0), 2: (0, 1), 3: (0, 2), 4: (1, 0), 5: (1, 1), 6: (1, 2), 7: (2, 0), 8: (2, 1), 9: (2, 2), 0: (3, 1)}
		ans = 0
		dp = {}
		for i in range(10):
			(r, c) = d[i]
			ans += self.helper(r, c, grid, 0, N, dp)
		return ans

	def helper(self, i, j, grid, curr, n, dp):
		if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == -1):
			return 0
		if curr == n - 1:
			return 1
		if (i, j, curr) in dp:
			return dp[i, j, curr]
		dp[i, j, curr] = self.helper(i - 1, j, grid, curr + 1, n, dp) + self.helper(i + 1, j, grid, curr + 1, n, dp) + self.helper(i, j - 1, grid, curr + 1, n, dp) + self.helper(i, j + 1, grid, curr + 1, n, dp) + self.helper(i, j, grid, curr + 1, n, dp)
		return dp[i, j, curr]


class Solution:

	def getCount(self, N):
		graph = [[-1, -1, -1, -1, -1], [-1, 1, 2, 3, -1], [-1, 4, 5, 6, -1], [-1, 7, 8, 9, -1], [-1, -1, 0, -1, -1], [-1, -1, -1, -1, -1]]
		dp = []
		for i in range(N):
			dp.append([1] * 10)
		for i in range(10):
			dp[0][i] = 1
		for i in range(1, N):
			for j in range(1, 5):
				for k in range(1, 4):
					if graph[j][k] != -1:
						sumu = 0
						if graph[j][k - 1] != -1:
							sumu += dp[i - 1][graph[j][k - 1]]
						if graph[j - 1][k] != -1:
							sumu += dp[i - 1][graph[j - 1][k]]
						if graph[j + 1][k] != -1:
							sumu += dp[i - 1][graph[j + 1][k]]
						if graph[j][k + 1] != -1:
							sumu += dp[i - 1][graph[j][k + 1]]
						if graph[j][k] != -1:
							sumu += dp[i - 1][graph[j][k]]
						dp[i][graph[j][k]] = sumu
		return sum(dp[-1])


class Solution:

	def getCount(self, N):
		d = [[0, 8], [1, 2, 4], [2, 3, 5, 1], [3, 2, 6], [4, 1, 5, 7], [5, 6, 4, 2, 8], [6, 3, 5, 9], [7, 4, 8], [8, 7, 9, 5, 0], [9, 8, 6]]
		l = [1] * 10
		l_new = [0] * 10
		for dig in range(1, N):
			for i in range(10):
				temp_sum = [l[x] for x in d[i]]
				l_new[i] = sum(temp_sum)
			l = l_new.copy()
		return sum(l)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def getCount(self, l):
		keys = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		dp = [[[-1 for i in range(l + 1)] for j in range(4)] for k in range(4)]

		def possibleNums(n, r, c):
			if keys[r][c] == -1:
				return 0
			if n == 1:
				return 1
			if dp[r][c][n] != -1:
				return dp[r][c][n]
			temp2 = possibleNums(n - 1, r, c)
			if r > 0:
				temp2 += possibleNums(n - 1, r - 1, c)
			if r < 3:
				temp2 += possibleNums(n - 1, r + 1, c)
			if c > 0:
				temp2 += possibleNums(n - 1, r, c - 1)
			if c < 2:
				temp2 += possibleNums(n - 1, r, c + 1)
			dp[r][c][n] = temp2
			return temp2
		temp = 0
		for i in range(10):
			if i == 0:
				temp += possibleNums(l, 3, 1)
			elif i >= 1 and i <= 3:
				temp += possibleNums(l, 0, i - 1)
			elif i >= 4 and i <= 6:
				temp += possibleNums(l, 1, i - 4)
			else:
				temp += possibleNums(l, 2, i - 7)
		return temp


memo = {}

class Solution:

	def helper(self, i, j, N, board):
		global memo
		if i < 0 or j < 0 or i >= 4 or (j >= 3) or (board[i][j] == -1):
			return 0
		if N == 1:
			return 1
		if (i, j, N) in memo:
			return memo[i, j, N]
		else:
			up = self.helper(i - 1, j, N - 1, board)
			down = self.helper(i + 1, j, N - 1, board)
			left = self.helper(i, j - 1, N - 1, board)
			right = self.helper(i, j + 1, N - 1, board)
			stay = self.helper(i, j, N - 1, board)
			memo[i, j, N] = up + down + left + right + stay
			return memo[i, j, N]

	def getCount(self, N):
		board = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		c = 0
		for i in range(4):
			for j in range(3):
				if board[i][j] == -1:
					continue
				c += self.helper(i, j, N, board)
		return c


class Solution:

	def solve(self, mat, i, j, n, dp):
		if i < 0 or j < 0 or i > 3 or (j > 2) or (mat[i][j] == -1):
			return 0
		if n == 1:
			return 1
		if dp[mat[i][j]][n] != 0:
			return dp[mat[i][j]][n]
		rem = self.solve(mat, i, j, n - 1, dp)
		up = self.solve(mat, i - 1, j, n - 1, dp)
		down = self.solve(mat, i + 1, j, n - 1, dp)
		left = self.solve(mat, i, j - 1, n - 1, dp)
		right = self.solve(mat, i, j + 1, n - 1, dp)
		dp[mat[i][j]][n] = rem + up + down + left + right
		return dp[mat[i][j]][n]

	def getCount(self, n):
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		dp = [[0 for i in range(n + 1)] for j in range(10)]
		ans = 0
		for i in range(4):
			for j in range(3):
				if mat[i][j] != -1:
					ans += self.solve(mat, i, j, n, dp)
		return ans


class Solution:

	def getCount(self, N):
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		r = len(mat)
		c = len(mat[0])

		def recurse(i, j, n, dp):
			if n == 1:
				return 1
			if 0 > i or (i >= r and 0 < j) or j >= c:
				return 0
			if dp[mat[i][j]][n] != -1:
				return dp[mat[i][j]][n]
			curr = recurse(i, j, n - 1, dp)
			left = right = bottom = up = 0
			if j - 1 >= 0 and mat[i][j - 1] != -1:
				left = recurse(i, j - 1, n - 1, dp)
			if i - 1 >= 0 and mat[i - 1][j] != -1:
				bottom = recurse(i - 1, j, n - 1, dp)
			if i + 1 < r and mat[i + 1][j] != -1:
				up = recurse(i + 1, j, n - 1, dp)
			if j + 1 < c and mat[i][j + 1] != -1:
				right = recurse(i, j + 1, n - 1, dp)
			dp[mat[i][j]][n] = curr + left + up + bottom + right
			return dp[mat[i][j]][n]
		total = 0
		dp = [[-1 for _ in range(N + 1)] for _ in range(10)]
		for i in range(r):
			for j in range(c):
				if mat[i][j] != -1:
					total += recurse(i, j, N, dp)
		return total


class Solution:

	def getCount(self, N):
		mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [-1, 0, -1]]
		dp = []
		for i in range(10):
			t = []
			for j in range(N + 1):
				t.append(0)
			dp.append(t)
		for k in range(1, N + 1):
			for i in range(4):
				for j in range(3):
					p = mat[i][j]
					if k == 1:
						if p != -1:
							dp[mat[i][j]][k] = 1
					elif p != -1:
						(a, b, c, d, e) = (0, 0, 0, 0, 0)
						if k - 1 > 0:
							a = dp[p][k - 1]
							if i - 1 >= 0 and mat[i - 1][j] != -1:
								b = dp[mat[i - 1][j]][k - 1]
							if j - 1 >= 0 and mat[i][j - 1] != -1:
								c = dp[mat[i][j - 1]][k - 1]
							if i + 1 < 4 and mat[i + 1][j] != -1:
								d = dp[mat[i + 1][j]][k - 1]
							if j + 1 < 3 and mat[i][j + 1] != -1:
								e = dp[mat[i][j + 1]][k - 1]
						dp[mat[i][j]][k] = a + b + c + d + e
		s = 0
		for i in range(4):
			for j in range(3):
				if mat[i][j] != -1:
					s += dp[mat[i][j]][N]
		return s


class Solution:

	def getCount(self, N):
		ct = 1
		mat = [[-1] * 3 for _ in range(4)]
		for r in range(3):
			for c in range(3):
				mat[r][c] = ct
				ct += 1
		mat[-1][1] = 0

		def isValid(r, c):
			if 0 <= r < 4 and 0 <= c < 3:
				if r == 3 and c != 1:
					return False
				return True
			return False
		x = [0, -1, 1, 0, 0]
		y = [0, 0, 0, -1, 1]
		dp = [[-1] * N for i in range(10)]

		def soln(ln, r, c):
			if ln == 1:
				return 1
			mat_val = mat[r][c]
			if dp[mat_val][ln - 1] != -1:
				return dp[mat_val][ln - 1]
			temp = 0
			for i in range(5):
				if isValid(r + x[i], c + y[i]):
					temp += soln(ln - 1, r + x[i], c + y[i])
			dp[mat_val][ln - 1] = temp
			return dp[mat_val][ln - 1]
		res = 0
		for i in range(3):
			for j in range(3):
				res += soln(N, i, j)
		res += soln(N, 3, 1)
		return res