<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>An integer is called <strong>good</strong> if its digits can be <em>rearranged</em> to form a <strong>k-palindromic</strong> integer. For example, for <code>k = 2</code>, 2020 can be rearranged to form the <em>k-palindromic</em> integer 2002, whereas 1010 cannot be rearranged to form a <em>k-palindromic</em> integer.</p>

<p>Return the count of <strong>good</strong> integers containing <code>n</code> digits.</p>

<p><strong>Note</strong> that <em>any</em> integer must <strong>not</strong> have leading zeros, <strong>neither</strong> before <strong>nor</strong> after rearrangement. For example, 1010 <em>cannot</em> be rearranged to form 101.</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">27</span></p>

<p><strong>Explanation:</strong></p>

<p><em>Some</em> of the good integers are:</p>

<ul>
	<li>551 because it can be rearranged to form 515.</li>
	<li>525 because it is already k-palindromic.</li>
</ul>
</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">2</span></p>

<p><strong>Explanation:</strong></p>

<p>The two good integers are 4 and 8.</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">2468</span></p>
</div>

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

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

class Solution:
    def combination(self, a, b):
        b = min(b, a-b)
        value = 1
        for num in range(a, a-b, -1):
            value*=num
        for num in range(2, b+1):
            value//=num
        return value

    def countGoodIntegers(self, n: int, k: int) -> int:
        if n==1:
            return sum(1 for d in range(1, 10) if d%k==0)
        l = n//2 - 1
        res = 0
        digits = set()
        for prev_num in range(10**l, 10**(l+1)):
            prev = str(prev_num)
            arr = [prev+str(d)+prev[::-1] for d in range(10)] if n&1 else [prev+prev[::-1]]
            for s in arr:
                if int(s)%k:
                    continue
                cnts = Counter(s)
                digits.add(tuple(sorted(cnts.items())))
        
        res = 0
        for digit in digits:
            # print(digit)
            length, total = n, 1
            for d, cnt in digit:
                total*=self.combination(length, cnt)
                length-=cnt
            res+=total
            if digit[0][0]=="0":
                length, total = n-digit[0][1],  self.combination(n-1, digit[0][1]-1)
                for d, cnt in digit[1:]:
                    total*=self.combination(length, cnt)
                    length-=cnt
                # print(total)
                res-=total

        return res

    def countGoodIntegers1(self, n: int, k: int) -> int:
        
        mem = {}
        def any_num(length, digit, one_digit=-1):
            key = (length, digit, one_digit)
            # print(key)
            if key in mem:
                return mem[key]
            if length == 0:
                return 1
            value = 0
            for d in range(digit, -1 ,-1):
                if one_digit==d:
                    continue
                _d = d-1
                for l in (range(1, length+1, 1) if length&1 else range(2, length+1, 2)): 
                    value+=pc(length, l)*any_num(length-l, _d, one_digit)
            mem[key] = value
            # print(key, value)
            return value

        t = 0
        if k==1:
            t = any_num(n, 9)
        return t//10*9- (9 if n&1 and n>=3 else 0)

19295