<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:
            return '8' + '9' * max(0, n - 2) + '8' * int(n > 1)
        if k == 4:
            return '8' * n if n < 5 else ("88" + '9' * (n - 4) + "88")
        if k == 5:
            return '5' + '9' * max(0, n - 2) + '5' * int(n > 1)
        if k == 6:
            if n < 3:
                return '6' * n
            elif n % 2 == 1:
                return '8' + '9' * ((n - 3) // 2) + '8' + '9' * ((n - 3) // 2) + '8'
            else:
                return '8' + '9' * ((n - 4) // 2) + "77" + '9' * ((n - 4) // 2) + '8'
        if k == 7:
            if n < 3:
                return '7' * n
            digits = [9] * n
            for i in range(9, -1, -1):
                if n % 2 == 1:
                    digits[n // 2] = i
                else:
                    digits[n // 2 - 1] = digits[n // 2] = i
                mod = 0
                for d in digits:
                    mod = (mod * 10 + d) % 7
                if mod == 0:
                    return ''.join(map(str, digits))
        if k == 8:
            return '8' * n if n < 7 else ("888" + '9' * (n - 6) + "888")

24691