MBIPALIN - Bipalindrome

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


Added by:psetter
Date:2009-03-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 08

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.