<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:
        arr = []
        
        def get7():                     
            for i in range(9, 1, -1):
                if n&1:
                    arr[n//2]=i
                else:
                    arr[n//2]=arr[n//2-1]=i
                if valid():
                    return
        
        def valid():
            m = 0
            for x in arr:
                m=(m*10+x)%7
            return m==0

        if k==1 or k==3 or k==9:
            arr = '9'*n
        elif k==8:
            if n<7:
                arr = '8'*n
            else:
                arr.append('888')
                arr.append('9'*(n-6))
                arr.append('888')
        elif k==2:
            arr.append('8')
            if n>2: arr.append('9'*(n-2))                
            if n>1: arr.append('8')
        elif k==4:
            if n<=4:
                arr = '8'*n
            else:
                arr.append('88')
                arr.append('9'*(n-4))
                arr.append('88')
        elif k==5:
            arr.append('5')
            if n>2: arr.append('9'*(n-2))   
            if n>1: arr.append('5')
        elif k==6:
            if n<=2:
                arr = '6'*n
            elif n==3:
                arr.append('888')
            elif n==4:
                arr.append('8778')
            else:
                arr.append('8')
                arr.append('9'*((n-3)//2))
                if n&1:
                    arr.append('8')
                else:
                    arr.append('77')
                arr.append('9'*((n-3)//2))
                arr.append('8')
        else:
            if n<3:
                arr = '7'*n
            else:
                arr = [9]*n
                get7()
                arr = map(str, arr)
        return ''.join(arr)
24691