Untitled

import java.util.HashMap;
import java.util.Map;

public class KnightDialer {

    private static final int MOD = 1_000_000_007;

    public static int knightDialer(int n) {
        // Knight moves map
        int[][] moves = {
            {4, 6},      // 0
            {6, 8},      // 1
            {7, 9},      // 2
            {4, 8},      // 3
            {3, 9, 0},   // 4
            {},          // 5 (invalid)
            {1, 7, 0},   // 6
            {2, 6},      // 7
            {1, 3},      // 8
            {2, 4}       // 9
        };

        // Memoization map
        Map<String, Integer> memo = new HashMap<>();

        // Calculate the total ways
        int totalWays = 0;
        for (int i = 0; i <= 9; i++) {
            totalWays = (totalWays + countWays(i, n - 1, moves, memo)) % MOD;
        }
        return totalWays;
    }

    private static int countWays(int pos, int movesLeft, int[][] moves, Map<String, Integer> memo) {
        // Base case: no moves left, 1 way to stay on the current position
        if (movesLeft == 0) {
            return 1;
        }

        // Memoization key
        String key = pos + "," + movesLeft;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Recursive case: explore all valid moves
        int totalWays = 0;
        for (int nextPos : moves[pos]) {
            totalWays = (totalWays + countWays(nextPos, movesLeft - 1, moves, memo)) % MOD;
        }

        // Store the result in the memo map
        memo.put(key, totalWays);
        return totalWays;
    }

    public static void main(String[] args) {
        System.out.println(knightDialer(1)); // Output: 10
        System.out.println(knightDialer(2)); // Output: 20
        System.out.println(knightDialer(3131)); // Output: 136006598
    }
}