<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:
        @cache
        def tenN_mod_k(n):
            if n == 0:
                return 1%k
            else:
                return ((10%k)*tenN_mod_k(n-1)) % k
        '''
        
        @cache
        def dp(n,m):
            if n == 1:
                return str(max([i for i in range(10) if i%k == m], default=''))
            elif n == 2:
                return str(max([i*11 for i in range(10) if i%k == m], default=''))
            for d in reversed(range(10)):
                base = (d*tenN_mod_k(n-1)+d)%k
                s = max([dp(n-2, x%k) for x in reversed(range(10)) if (base+x*10)%k == m], default='')
                if s:
                    return f'{d}{s}{d}'
            return ''
        return dp(n,0)
        '''
        base = 1 if n%2 == 1 else 11
        dp = [str(max([(i*base) for i in range(10) if (i*base)%k == kk], default='')) for kk in range(k)]
        base = 2 if n%2==0 else 1
        #print(dp)
        #tenN_mod_k = 10**(base)%k
        for nn in range(base,n,2):
            #print(nn,dp)
            tmp = [''] * k
            #tenN_mod_k = (tenN_mod_k*100)%k
            for kk in reversed(range(k)):
                for d in reversed(range(10)):
                    base = (d*tenN_mod_k(nn+1)+d)%k
                    s = max([dp[x%k] for x in reversed(range(10)) if (base+x*10)%k == kk], default='')
                    #print('==>' ,nn, kk, d, base,tenN_mod_k(nn+2), xxxx)
                    #s = max(xxxx, default='')
                    if s:
                        tmp[kk] = f'{d}{s}{d}'
                        break
            #print(nn,tmp, "end")
            dp = tmp
        return dp[0]
99276