<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 largestPalindrome(self, n: int, k: int) -> str:
        """

        """
        # (80000 % k) + (9000 % k) + (800 % k) + (90 % k) + (8 % k)) % k == 89898 % k
        # use digit dp.

        a = [[0 for _ in range(10)] for _ in range(n)]
        for j in range(10):
            a[n-1][j] = j%k

        for i in reversed(range(n-1)):
            for j in range(10):
                a[i][j] = (a[i+1][j] * 10) % k

        dp = [[None for _ in range(10)] for _ in range(n)]
        res = [None] * n 

        def go(i, r):
            if i == (n+1)//2: return r == 0
            if dp[i][r] != None: return dp[i][r]
            for j in reversed(range(int(i==0), 10)):
                new_r = r + a[i][j] 
                if n%2 == 0 or i != n//2: new_r+=a[n-i-1][j]
                new_r%=k
                if go(i+1, new_r):
                    res[i] = res[n-i-1] = str(j)
                    dp[i][r] = True
                    return True
            dp[i][r] = False
            return False
        go(0, 0)

        return ''.join(res)
72638