Concatenated Palindromes

Time limit1sMemory limit128 MB

Summary

Count N-digit numbers formed by concatenating two equal-length palindromes (first not starting with 0) that are divisible by M.

Level: Hard8 of 10
Topics: Combinatorics, Math, Number theory
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples3

Example 1
Input
```
6 12345
```
Expected output
```
1
```
Example 2
Input
```
2 10
```
Expected output
```
9
```
Example 3
Input
```
6 123
```
Expected output
```
71
```