<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:
        tens_mods = [[0 for _ in range(10)] for _ in range(n)]
        for d in range(1,10):
            tens_mods[0][d] = d % k
        for i in range(1,n):
            for d in range(1,10):
                tens_mods[i][d] = ((10 % k) * (tens_mods[i-1][d])) % k
        half_n = int((n-1) // 2)
        dp = [[-1 for _ in range(k)] for _ in range(half_n+1)]
        for d in range(10):
            cur_mod = (tens_mods[half_n][d] + (tens_mods[n-half_n-1][d] if n % 2 == 0 else 0)) % k
            dp[-1][cur_mod] = d
        for i in range(half_n-1,-1,-1):
            for d in range(10):
                cur_mod = (tens_mods[i][d] + tens_mods[n-i-1][d]) % k
                for prev_mod,prev_digit in enumerate(dp[i+1]):
                    if prev_digit >= 0:
                        next_mod = (cur_mod + prev_mod) % k
                        dp[i][next_mod] = d
        #print(tens_mods)
        #print(dp)
        # work backwards, seeking prior row that "undoes" current mod to get actual mod
        res = ""
        cur_mod = 0
        for i in range(int(n//2)):
            cur_digit = dp[i][cur_mod]
            expected_mod = (tens_mods[i][cur_digit] + tens_mods[n-i-1][cur_digit]) % k
            res=str(cur_digit) + res
            cur_mod = (cur_mod - expected_mod) % k
        if n % 2 == 0:
            return res[::-1] + res
        return res[::-1] + str(dp[half_n][cur_mod]) + res

46001