시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 42 7 5 50.000%

문제

상근이와 정인이는 수학을 사랑한다. 상근이는 매우 창의적이어서 새로운 아이디어를 잘 낸다. 정인이는 몇 일 동안 상근이의 아이디어를 이해한다.

어느날 상근이와 정인이는 팰린드롬을 배웠다. 팰린드롬은 앞에서 읽을 때와, 뒤에서 읽을 때 같은 문자열이다. 예를 들면, "ANA", "1991", "RADAR"는 팰린드롬이다.

몇일 뒤, 상근이는 팰린드롬에 대한 새로운 개념을 생각해냈다. 바로 "붙인드롬"이다.

붙인드롬은 숫자이고, 같은 길이의 팰린드롬 2개를 붙인 것이다. 이 두 팰린드롬은 모두 숫자로 이루어져 있고, 첫 팰린드롬의 첫 번째 자리는 0이 아니다. 

예를 들어, 393020은 붙인드롬이다. (두 팰린드롬 393, 020을 여서 만들 수 있다) 하지만, 222와 010202는 붙인드롬이 아니다.

정인이는 이 붙인드롬에 대해서 30분정도 고민하다 보니, 6자리 붙인드롬 중에서 12345로 나누어 떨어지는 것은 555525 하나라는 것을 알게 되었다.

정인이는 상근이보다 뛰어나다는 점을 강조하기 위해서, N자리 붙인드롬 중에서 M으로 나누어 떨어지는 것의 개수를 구하려고 한다.

N과 M이 주어졌을 때, N자리 붙인드롬 중, M으로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ 1,000,000) N은 짝수이다.

출력

첫째 줄에, N자리 붙인드롬 중에서 M으로 나누어 떨어지는 것의 개수를 출력한다.

예제 입력

6 12345

예제 출력

1

힌트