<p>You are given two <strong>positive</strong> integers <code>n</code> and <code>k</code>.</p>

<p>An integer <code>x</code> is called <strong>k-palindromic</strong> if:</p>

<ul>
	<li><code>x</code> is a <span data-keyword="palindrome-integer">palindrome</span>.</li>
	<li><code>x</code> is divisible by <code>k</code>.</li>
</ul>

<p>Return the<strong> largest</strong> integer having <code>n</code> digits (as a string) that is <strong>k-palindromic</strong>.</p>

<p><strong>Note</strong> that the integer must <strong>not</strong> have leading zeros.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 3, k = 5</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;595&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>595 is the largest k-palindromic integer with 3 digits.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1, k = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;8&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>4 and 8 are the only k-palindromic integers with 1 digit.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 5, k = 6</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;89898&quot;</span></p>
</div>

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

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 9</code></li>
</ul>

class Solution:
    def compute_powers(self, n, k):
        powers = [1] * (n + 1)
        for i in range(1, n + 1):
            powers[i] = (powers[i - 1] * 10) % k
        return powers

    def dfs(self, current, index, curr_mod, n, k, powers, memo):
        if index > n // 2 or (index == n // 2 and n % 2 == 0):
            return "".join(current) if curr_mod == 0 else ""

        key = (index, curr_mod)
        if key in memo:
            return memo[key]

        res = ""
        start = 1 if index == 0 else 0
        for c in range(9, start - 1, -1):
            c_char = str(c)
            current[index] = c_char
            if index < n - index - 1:
                current[n - index - 1] = c_char
            new_mod = (curr_mod + c * (powers[index] + (powers[n - index - 1] if index != n - index - 1 else 0))) % k
            temp = self.dfs(current, index + 1, new_mod, n, k, powers, memo)
            if temp:
                if temp > res:
                    res = temp
                    break
            current[index] = '#'
            if index < n - index - 1:
                current[n - index - 1] = '#'

        memo[key] = res
        return res

    def largestPalindrome(self, n: int, k: int) -> str:
        powers = self.compute_powers(n, k)
        current = ['#'] * n
        memo = {}
        result = self.dfs(current, 0, 0, n, k, powers, memo)
        return result
109931