<p>The chess knight has a <strong>unique movement</strong>,&nbsp;it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an <strong>L</strong>). The possible movements of chess knight are shown in this diagram:</p>

<p>A chess knight can move as indicated in the chess diagram below:</p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/18/chess.jpg" style="width: 402px; height: 402px;" />
<p>We have a chess knight and a phone pad as shown below, the knight <strong>can only stand on a numeric cell</strong>&nbsp;(i.e. blue cell).</p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/18/phone.jpg" style="width: 242px; height: 322px;" />
<p>Given an integer <code>n</code>, return how many distinct phone numbers of length <code>n</code> we can dial.</p>

<p>You are allowed to place the knight <strong>on any numeric cell</strong> initially and then you should perform <code>n - 1</code> jumps to dial a number of length <code>n</code>. All jumps should be <strong>valid</strong> knight jumps.</p>

<p>As the answer may be very large, <strong>return the answer modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 10
<strong>Explanation:</strong> We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 20
<strong>Explanation:</strong> All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 3131
<strong>Output:</strong> 136006598
<strong>Explanation:</strong> Please take care of the mod.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 5000</code></li>
</ul>

from functools import lru_cache
class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10**9 + 7
        
        @lru_cache(None)
        def generate_possible_jumps(r: int, c: int):
            directions = [
                (-2, -1), (-2, 1), (-1, -2), (-1, 2),
                (2, -1), (2, 1), (1, -2), (1, 2)
            ]
            res = []
            for dr, dc in directions:
                new_r, new_c = r + dr, c + dc
                if 0 <= new_r < 4 and 0 <= new_c < 3 and (new_r, new_c) not in [(3, 0), (3, 2)]:
                    res.append((new_r, new_c))
            return res
        
        @lru_cache(None)
        def backtrack(curr_row: int, curr_col: int, remaining_jumps: int):
            if remaining_jumps == 0:
                return 1
            
            count = 0
            possible_jumps = generate_possible_jumps(curr_row, curr_col)
            for next_row, next_col in possible_jumps:
                count = (count + backtrack(next_row, next_col, remaining_jumps - 1)) % MOD
            
            return count

        total_count = 0
        for i in range(4):
            for j in range(3):
                if (i, j) not in [(3, 0), (3, 2)]:
                    total_count = (total_count + backtrack(i, j, n - 1)) % MOD

        return total_count

"""
n is the length of the phone number, n is always >= 0
4 rows 3 cols

i start by iterating over this 4x3 grid besides locations [3,0] and [3,2] non number cells
i know i have n jumps to start with. i would generate all possible jumps at that point

def backtrack(curr_row, curr_col, remaining_jumps):
    if curr_num_of_jumps == n-1:
        i know this is valid, res.append(total count + 1)
    generate possible jumps from current location using curr_row and curr_col
    for all possible jumps:
        at each point, i can either jump to that cell
        explore from there, remaining_jumps -1
        i can skip jumping from this cell

"""
45509