<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 sol6(l,r,rem):
            if l==r:
                if rem==2:
                    ans[l]="7"
                if rem==1:
                    ans[l]="8"
                if rem==0:
                    ans[l]="9"
                return
            if l==r-1:
                if rem==0:
                    ans[l]="9"
                    ans[r]="9"
                if rem==1:
                    ans[l]="7"
                    ans[r]="7"
                if rem==2:
                    ans[l]="8"
                    ans[r]="8"
                return
            
            ans[l]="9"
            ans[r]="9"
            sol6(l+1,r-1,rem)
            
        def sol7(l, r, rem):
            if l > r:
                return rem == 0
            if l == r:
                for d in range(9, -1, -1):
                    if (rem * 10 + d) % 7 == 0:
                        ans[l] = str(d)
                        return True
                return False
            for d in range(9, -1, -1):
                new_rem = (rem * 100 + d * 10 + d) % 7
                ans[l] = str(d)
                ans[r] = str(d)
                if sol7(l + 1, r - 1, new_rem):
                    return True
            return False

        ans=["0" for _ in range(n)]
        if k==1:
            ans=["9" for _ in range(n)]
        if k == 2:
            ans=["9" for _ in range(n)]
            ans[0]="8"
            ans[-1]="8"
        elif k == 3 or k == 9 or k == 5:
            ans=["9" for _ in range(n)]
            if k == 5:
                ans[0]="5"
                ans[-1]="5"
        elif k == 6:
            if n == 2:
                return "66"
            elif n == 1:
                return "6"
            else:
                ans=["0" for _ in range(n)]
                ans[0]="8"
                ans[-1]="8"
                sol6(1, n - 2, 1)
        elif k == 4:
            if n <= 4:
                return "8" * n
            ans[0]="8"
            ans[-1]="8"
            ans[-2]="8"
            ans[1]="8"
            for i in range(2, n - 2):
                ans[i]="9"
        elif k == 8:
            if n <= 6:
                return "8" * n
            for i in range(3):
                ans[i]="8"
                ans[n - i - 1]="8"
            for i in range(3, n - 3):
                ans[i]="9"
        elif k == 7:
            if n == 1:
                return "7"
            if n == 2:
                return "77"
            
            ans=["9" for _ in range(n)]
            if n%2==0:
                r=n//2
                l=r-1
            
                for i in range(9,-1,-1):
                    ans[l]=str(i)
                    ans[r]=str(i)
                    rem=0
                    for j in range(n):
                        rem=(rem*10+int(ans[j]))%7
                    if rem==0:
                        break
            else:
                r=n//2
                for i in range(9,-1,-1):
                    # ans[l]=str(i)
                    ans[r]=str(i)
                    rem=0
                    for j in range(n):
                        rem=(rem*10+int(ans[j])) % 7
                    if rem==0:
                        break
        return "".join(ans)


30018