<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 == 5:
            toadd = ""
            if n > 1:
                toadd = '5'
            return '5'+'9'*(n-2) + toadd
        if k == 3 or k == 9 or k == 1:
            return '9'*n
        if k == 2:
            toadd = ''
            if n > 1:
                toadd = '8'
            return '8'+'9'*(n-2) + toadd
        if k == 4:
            if n <= 4:
                return '8'*n
            return '88'+'9'*(n-4)+'88'
        if k == 8:
            if n <= 6:
                return '8'*n
            return '888'+'9'*(n-6)+'888'
        # if k == 7:
        #     return
            
        od = {}
        cur = 1
        for i in range (n):
            od[n-i-1] = cur%k
            cur*=10
        mydict = {}
        def dfs(p1,p2,mod,hasl):
            if p1 > p2:
                if mod == 0:
                    return [True,""]
                return [False,""]
            if (p1,mod,hasl) in mydict:
                return mydict[(p1,mod,hasl)]
            lz = od[p1]
            rz = od[p2]
            if p2-p1 > 1 and k == 7:
                cur = dfs(p1+1,p2-1,(mod+9*lz+9*rz)%k, False)
                if cur[0]:
                    flag = True
                    res = '9'+cur[1]+'9'
                    return [flag,res]       
            res = ""
            flag = False
            if hasl:
                for i in range (9,0,-1):
                    if p1 == p2:
                        cur = dfs(p1+1,p2-1,(mod+i*rz)%k, False)
                    else:
                        cur = dfs(p1+1,p2-1,(mod+i*lz+i*rz)%k, False)
                    if cur[0]:
                        flag = True
                        if p1 == p2:
                            res = str(i)+cur[1]
                        else:
                            res = str(i)+cur[1]+str(i)
                        break
            else:
                for i in range (9,-1,-1):
                    if p1 == p2:
                        cur = dfs(p1+1,p2-1,(mod+i*rz)%k, hasl)
                    else:
                        cur = dfs(p1+1,p2-1,(mod+i*lz+i*rz)%k, hasl)
                    if cur[0]:
                        flag = True
                        if p1 == p2:
                            res = str(i)+cur[1]
                        else:
                            res = str(i)+cur[1]+str(i)
                        break
            mydict[(p1,mod,hasl)] = [flag,res]
            return [flag,res]
        c = dfs(0,n-1,0,True)
        return c[1]
77966