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


@lru_cache(None)
def poww(a,b,k):
    return pow(a,b,k)

class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
#         89898 8 10**5
#         80000   
#         8     8 10**0
        
#         9000  
#         90
#         800
        if k==1:
            return "9"*n
        
        arr = [] 
        nn = n//2 + n%2
        t=[]
        @lru_cache(None)
        def compute(i, mod):
            if i >= nn:
                if mod == 0:
                    # print(t,arr)
                    # return "".join(map(str, arr)) + "".join(map(str, arr[-(1 if n * 2 > len(arr) else 0)::-1]))
                    a = []
                    b = []
                    # arr.sort()
                    mid= ""
                    if len(arr)%2==1:
                        mid = str(arr[-1])
                    # mid= str(value)
                    for x in  range(len(arr) - (len(arr)%2)):
                        if x%2==0:
                            a.append(arr[x])
                        else:
                            b.append(arr[x])
                    # a.sort()
                    # b.sort()
                    b.reverse()
                    return "".join(map(str,a)) + mid + "".join(map(str,b))
                        
                return None

            if i == nn - 1 and n%2==1:
                # print("F")
                for j in range(9, 0, -1):
                    a = j * poww(10, n//2, k)
                    c = a % k
                    arr.append(j)
                    # t.append(j*pow(10, n//2))
                    result = compute(i + 1, (mod + c) % k)
                    
                    
                    # t.pop()
                    if result:
                        return result
                    arr.pop()
                    
                return None

            for j in range(9, 0, -1):
                a = j * poww(10, i, k)
                b = j * poww(10, n - i - 1, k)
                c = (a + b) % k
                arr.append(j)
                arr.append(j)
                # t.append(j*pow(10, i))
                # t.append(j*pow(10, n - i - 1))
                # print(arr)
                result = compute(i + 1, (mod + c) % k)
                
                
                # t.pop()
                # t.pop()
                if result:
                    return result
                arr.pop()
                arr.pop()

            return None
        r= compute(0, 0)
        compute.cache_clear()
        return r
        
poww.cache_clear()
            
205826