<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:
        smodk = [1]
        for _ in range(1, n): smodk.append((10*smodk[-1])%k)
        modk = smodk[:(n+1)//2]
        for i in range(n//2): modk[i] += smodk[n-1-i]
        
        m0 = (10*smodk[-1] - 1) % k # find min palindrome with this modular
        while modk and not modk[-1]: modk.pop()
        nm = len(modk); evenafter = []; even = True
        for j in range(nm-1, -1, -1): even &= (~modk[j]&1); evenafter.append(even)
        evenafter = evenafter[::-1]
        @cache
        def dp(j, m):
            if j >= len(modk): return None if m > 0 else []
            if (m&1) and (~k&1) and evenafter[j]: return None
            for d in range(10):
                dmod = (d*modk[j]) % k
                v = dp(j+1, (m-dmod)%k)
                if v is None: continue
                v.append(d)
                return v
            return None
        res = [9] * n; subf = dp(0, m0)[::-1]
        for i, vs in enumerate(subf):
            res[i] -= vs; res[n-1-i] = res[i]
        return ''.join(str(f) for f in res)
88621