<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>

# P = [1]  + [0] * (10 ** 5)
# for i in range(1, 10 ** 5 + 1):
#     P[i] = P[i - 1] * 10 % 7

class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        P = [1]  + [0] * (10 ** 5)
        for i in range(1, 10 ** 5 + 1):
            P[i] = P[i - 1] * 10 % k
        
        ans = [''] * n
        m = (n + 1) // 2
        seen = [[False] * k for _ in range(m + 1)]
        
        # @cache
        def dfs(i, z):
            if i == m: return z == 0
            seen[i][z] = True
            for x in range(9, -1, -1):
                if n % 2 and i == m - 1:
                    y = (x * P[i] + z) % k
                else:
                    y = (x * (P[i] + P[n - 1 - i]) + z) % k
                if not seen[i + 1][y] and dfs(i + 1, y):
                    ans[i] = ans[n - 1 - i] = str(x)
                    return True
            return False
            
        dfs(0, 0)
        return ''.join(ans)

        # if k in [1, 3, 9]: return '9' * n
        # if k == 2:
        #     if n == 1: return '8'
        #     return '8' + '9' * (n - 2) + '8'
        # if k == 4:
        #     if n == 1: return '8'
        #     if n == 2: return '88'
        #     if n == 3: return '888'
        #     return '88' + '9' * (n - 4) + '88'
        # if k == 5:
        #     if n == 1: return '5'
        #     return '5' + '9' * (n - 2) + '5'
        # if k == 6:
        #     if n == 1: return '6'
        #     if n == 2: return '66'
        #     x = n - 2
        #     y = x // 2
        #     if x % 2: return '8' + '9' * y + '8' + '9' * y + '8'
        #     return '8' + '9' * (y - 1) + '77' + '9' * (y - 1) + '8'
        # if k == 8:
        #     if n <= 5: return '8' * n
        #     return '888' + '9' * (n - 6) + '888'
        # if k == 7:
        #     if n % 2:
        #         x = n // 2
        #         for a in range(9, -1, -1):
        #             cur = ((P[x] - 1) * P[x + 1] + a * P[x] + (P[x] - 1)) % 7
        #             if not cur:
        #                 return '9' * x + str(a) + '9' * x
        #     else:
        #         x = n // 2 - 1
        #         for a in range(99, -1, -11):
        #             cur = ((P[x] - 1) * P[x + 2] + a * P[x] + (P[x] - 1)) % 7
        #             if not cur:
        #                 return '9' * x + str(a) + '9' * x
            
                    
                    
                            
            
67311