<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:
        '''
        if k in {1, 3, 9}:
            return '9'*n
        if k == 2:
            if n <= 2:
                return '8'*n
            return '8'+ '9'*(n-2) + '8'
        elif k == 4:
            if n <= 3:
                return '8'*n
            return '88' + '9'*(n-4) + '88'
        elif k == 8:
            if n <= 6:
                return '8'*n
            return '888' + '9'*(n-6) + '888'
        elif k == 5:
            return '5'+'9'*(n-2)+'5' if n >= 2 else '5'*n
        elif k == 6:
            if n <= 2:
                return '6'*n
            if n%2 == 1:
                mid = '9'*((n-3)//2)
                return '8' + mid + '8' + mid + '8'
            else:
                mid = '9'*((n-4)//2)
                return '8' + mid + '77' + mid + '8'
        else:
            if n <= 2:
                return '7'*n
            todo = '9'*((n-1)//2)+"{0}"+'9'*((n-1)//2) if n%2 == 1 else '9'*((n-2)//2)+"{0}{1}"+'9'*((n-2)//2)
            for mid in range(9, 0, -1):
                res = todo.format(mid, mid)
                acc = 0
                for d in res:
                    acc = (acc*10 + int(d))%k
                if acc == 0:
                    return res
        '''
        res = [""]*n
        pow10 = [1]
        for _ in range(1, n):
            pow10.append((pow10[-1]*10)%k)
        @cache
        def dp(l, mod):
            r = n - 1 - l
            if l > r:
                return mod==0
            for d in range(9, -1, -1):
                nxt_mod = (mod + ((d%k)*pow10[l])%k )%k
                if l < r:
                    nxt_mod = (nxt_mod + ((d%k)*pow10[r])%k )%k
                if dp(l+1, nxt_mod):
                    res[l] = res[r] = str(d)
                    return True
            return False
        dp(0, 0)
        dp.cache_clear()
        return "".join(res)
184516