<p>A <strong>k-mirror number</strong> is a <strong>positive</strong> integer <strong>without leading zeros</strong> that reads the same both forward and backward in base-10 <strong>as well as</strong> in base-k.</p>

<ul>
	<li>For example, <code>9</code> is a 2-mirror number. The representation of <code>9</code> in base-10 and base-2 are <code>9</code> and <code>1001</code> respectively, which read the same both forward and backward.</li>
	<li>On the contrary, <code>4</code> is not a 2-mirror number. The representation of <code>4</code> in base-2 is <code>100</code>, which does not read the same both forward and backward.</li>
</ul>

<p>Given the base <code>k</code> and the number <code>n</code>, return <em>the <strong>sum</strong> of the</em> <code>n</code> <em><strong>smallest</strong> k-mirror numbers</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> k = 2, n = 5
<strong>Output:</strong> 25
<strong>Explanation:
</strong>The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> k = 3, n = 7
<strong>Output:</strong> 499
<strong>Explanation:
</strong>The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> k = 7, n = 17
<strong>Output:</strong> 20379000
<strong>Explanation:</strong> The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= k &lt;= 9</code></li>
	<li><code>1 &lt;= n &lt;= 30</code></li>
</ul>

class Solution:
    def kMirror(self, k: int, n: int) -> int:

        # def generate_palindromes(k, n, curr):
        #     nonlocal l
        #     print("curr is " + curr)
        #     if len(l) >= n:
        #         return
        #     if len(curr) >= 18:
        #         print("in here yo")
        #         return
        #     if curr and int(curr, k) > 0:
        #         l.append(curr)
        #         print("appending " + curr)


        #     if (len(curr) == 1 and int(curr) < k):
        #         print("it's only 1 digit")
        #         generate_palindromes(k, n, str(int(curr) + 1))
        #     elif len(curr) == 1:
        #         pass
        #     elif len(curr) == 0:
        #         generate_palindromes(k, n, "1")
        #         for i in range(1,k):
        #             generate_palindromes(k, n, str(i) + curr + str(i))
            
        #     else:
        #         for i in range(1,k):
        #             generate_palindromes(k, n, str(i) + curr + str(i))
        #     # for i in range(1, k):
        #     #     print("i is " + str(i))
        #     #     generate_palindromes(k, n, str(i))

        #     # for i in range(1,k):
        #     #     generate_palindromes(k, n, str(i) + curr + str(i))
            

        # def convert_to_base10(k, num):
        #     ret = 0
        #     for i in range(len(num)-1, -1, -1):
        #         ret += int(num[i])*k**i
        #     return ret
        
        # total = 0
        # l = []
        # generate_palindromes(k,n,"")
        # # for i in range(1, k):
        # #     generate_palindromes(k, n, str(i))
        # #     if len(l) >= n:
        # #         print("in here")
        # #         break
        # print(l)
        # for num in l:
        #     total += convert_to_base10(k, num)
        
        # return total

        def is_palindrome(s: str) -> bool:
            return s == s[::-1]

        def to_base_k(num: int, k: int) -> str:
            result = []
            while num > 0:
                result.append(str(num % k))
                num //= k
            return ''.join(result[::-1])

        def generate_palindromes(n: int, k: int) -> int:
            def generate_candidates(length: int) -> list:
                if length == 1:
                    return [str(i) for i in range(1, 10)]
                half = (length + 1) // 2
                result = []
                for num in range(10**(half - 1), 10**half):
                    if length % 2 == 0:
                        result.append(str(num) + str(num)[::-1])
                    else:
                        result.append(str(num) + str(num)[::-1][1:])
                return result
            
            total_sum = 0
            found = 0
            length = 1
            
            while found < n:
                candidates = generate_candidates(length)
                for candidate in candidates:
                    num = int(candidate)
                    if is_palindrome(to_base_k(num, k)):
                        total_sum += num
                        found += 1
                        if found == n:
                            return total_sum
                length += 1
            
            return total_sum

        result = generate_palindromes(n, k)
        return result
            

87400