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

check = [0, 9, 4, 3, 2, 1, 1, 1, 1, 1]
factorials = [1]
for i in range(1, 11):
    factorials.append(factorials[-1] * i)
class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        if n == 1: return check[k]
        pals = []
        digits = '0123456789'
        digs = []
        for i in range(n//2):
            digs.append(digits)
        digs[-1] = digs[-1][1:]
        if n & 1:
            digs = [digits] + digs
        poss = 0
        seen = set()
        for number in product(*digs):
            if n & 1:
                left = reversed(number[1:])
            else:
                left = reversed(number)
            pal = ''.join(left) + ''.join(number)

            if int(pal) % k == 0:
                if (u:=''.join(sorted(pal))) in seen: continue
                else: seen.add(u)
                curr = 0
                ctr = defaultdict(int)
                for i in pal:
                    ctr[i] += 1
                curr = factorials[len(pal)]
                for i in ctr:
                    curr //= factorials[ctr[i]]
                poss += curr
                minus = 0
                if ctr['0'] > 0:
                    minus += factorial(len(pal) - 1)
                    for i in ctr:
                        if i == '0': ctr[i] -= 1
                        minus //= factorials[ctr[i]]
                poss -= minus
        return poss
17964