<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:
        powers = [0]*n
        powers[0] = 1%k
        for i in range(1,n):
            powers[i] = (powers[i-1] * 10) % k
        
        state = [[-1]*k for _ in range(n)]

        @cache
        def rec(i, div):
            mid = (n-1) // 2
            if i > mid: return div == 0
            for j in range(9, -1, -1):
                add = 0
                if i == mid and n&1:
                    add = (j * powers[n-i-1]) % k
                else:
                    add = (j * powers[n-i-1]) % k
                    add = (add + j * powers[i]) % k
                if rec(i+1, (div + add) % k): 
                    state[i][div] = j
                    return True
            return False
        
        rec(0,0)

        ans = []
        div = 0
        for i in range((n+1)//2):
            ans.append(str(state[i][div]))
            j = state[i][div]
            
            add = 0
            if i == (n-1)//2 and n&1:
                add = (j*powers[n-i-1])%k
            else:
                add = (j*powers[n-i-1])%k
                add = (add + (j*powers[i]))%k
            
            div = (div+add)%k
        
        mid = n//2
        return "".join(ans+ans[:mid][::-1])
152551