Pero and Slavko are two students who love math. Pero is very creative and often comes up with new ideas. Slavko later spends days thinking about Pero's ideas. One day Pero and Slavko learned what a palindrome was: a string read the same in either direction (for example, "ANA", "1991" and "RADAR" are palindromes). Later that day Pero came up with a new concept – a bipalindrome (bipalin for short).

A bipalin is a number, composed of two palindromes of the same length. Both of these palindromes are strings of decimal digits, the first which may not start with the digit 0 (therefore, the entire bipalin may not start with a 0). For example, 393020 is a bipalin (composed of the palindromes 393 and 020), while 222 and 010202 are not.

After hearing about bipalins, Slavko started thinking. After half an hour he found that there is only one bipalin of length 6 that is divisible by 12345. This is the bipalin 555525. Shocked by this finding, he wants you to write a program that, given two integers N and M, calculates the number of different bipalins of length N that are divisible by M.

Input

Input consists of two integers N and M (2 ≤ N ≤ 20, 1 ≤ M ≤ 1 000 000), where N is even.

Output

Output the number of different bipalins of length N that are divisible by M.

Sample

Input:
6 123

Output:
71

Input:
2 10

Output:
9

Input:
6 12345

Output:
1