Problem

You are given two integers $n$ and $k$.

Count how many positive integers with exactly $n$ digits are good.

An $n$-digit integer is called good if its digits can be rearranged to form a palindrome that is divisible by $k$.

Two integers are considered different if their decimal representations are different, even if they contain the same digits in a different order.

Notes

• The integer must have exactly $n$ digits, so it cannot start with 0.
• A palindrome reads the same forward and backward.
• You only need to count integers that can be rearranged into at least one valid palindrome divisible by $k$.

Input Format

• Two integers n and k.

Output Format

• Return the number of good integers with exactly n digits.

Constraints

• $1 \le n \le 10$
• $1 \le k \le 9$
• Digits are decimal (0 to 9).

Hints

• For a palindrome, the multiset of digits is highly constrained: at most one digit may have an odd frequency.
• Instead of checking every integer directly, think in terms of digit counts and generate only palindromic candidates.
• Once a valid multiset of digits is found, count how many $n$-digit numbers can be formed from it without leading zeros.