<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:
        def check7(num, n):
            c1, c2 = 0, 0
            c1 += int(num[:n % 3]) if n % 3 else 0
            for i in range(n // 3):
                if i % 2:
                    c1 += int(num[n % 3 + i * 3:n % 3 + (i + 1) * 3])
                else:
                    c2 += int(num[n % 3 + i * 3:n % 3 + (i + 1) * 3])
            return abs(c1 - c2) % 7 == 0

        if k == 1 or k == 3 or k == 9:
            return "9" * n
        elif k == 2:
            return "8" + "9" * (n - 2) + "8" if n > 1 else "8"
        elif k == 4:
            if n <= 4:
                return "8" * n
            return "88" + "9" * (n - 4) + "88"
        elif k == 8:
            if n <= 6:
                return "8" * n
            return "888" + "9" * (n - 6) + "888"
        elif k == 5:
            return "5" + "9" * (n - 2) + "5" if n > 1 else "5"
        elif k == 6:
            if n == 1:
                return "6"
            elif n == 2:
                return "66"
            elif n % 2:
                return "8" + "9" * (n // 2 - 1) + "8" + "9" * (n // 2 - 1) + "8"
            else:
                return "8" + "9" * (n // 2 - 2) + "77" + "9" * (n // 2 - 2) + "8"
        elif k == 7:
            if n <= 2:
                return "7" * n
            if n % 2:
                for i in range(9, -1, -1):
                    num = "9" * (n // 2) + str(i) + "9" * (n // 2)
                    if check7(num, n):
                        return num
            else:
                for i in range(9, -1, -1):
                    num = "9" * (n // 2 - 1) + str(i) * 2 + "9" * (n // 2 - 1)
                    if check7(num, n):
                        return num
19363