Concatenated Palindromes

A concatenated palindrome is an N-digit number made by joining two palindrome digit strings of the same length. A palindrome reads the same forward and backward; for instance, "ANA", "1991", and "RADAR" are palindromes.

Each of the two parts must contain only digits and must itself be a palindrome. The first digit of the first part cannot be 0, while the second part may start with 0. Thus, 393020 is valid because it is 393 followed by 020. The numbers 222 and 010202 are not valid: the first cannot be split into two equal-length parts, and the second starts its first part with 0.

For instance, among six-digit concatenated palindromes, only 555525 is divisible by 12345.

Given N and M, count the N-digit concatenated palindromes that are divisible by M.

The first line contains N and M. (2 <= N <= 20, 1 <= M <= 1,000,000) N is even.

Print the number of N-digit concatenated palindromes that are divisible by M.