시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB458654.545%

문제

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

어느 날 상근이와 정인이는 팰린드롬을 배웠다. 팰린드롬은 앞에서 읽을 때와, 뒤에서 읽을 때 같은 문자열이다. 예를 들면, "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으로 나누어 떨어지는 것의 개수를 출력한다.

예제 입력 1

6 12345

예제 출력 1

1

예제 입력 2

2 10

예제 출력 2

9

예제 입력 3

6 123

예제 출력 3

71
W3sicHJvYmxlbV9pZCI6IjMxMzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjMjE4XHVkNTU5XHVjNzQ0IFx1YzBhY1x1Yjc5MVx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjllNFx1YzZiMCBcdWNjM2RcdWM3NThcdWM4MDFcdWM3NzRcdWM1YjRcdWMxMWMgXHVjMGM4XHViODVjXHVjNmI0IFx1YzU0NFx1Yzc3NFx1YjUxNFx1YzViNFx1Yjk3YyBcdWM3OTggXHViMGI4XHViMmU0LiBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHViYTcwXHVjZTYwIFx1YjNkOVx1YzU0OCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNTQ0XHVjNzc0XHViNTE0XHVjNWI0XHViOTdjIFx1Yzc3NFx1ZDU3NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwIFx1YjBhMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0NCBcdWJjMzBcdWM2ZTBcdWIyZTQuIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0MCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHVjNzdkXHVjNzQ0IFx1YjU0Y1x1YzY0MCwgXHViNGE0XHVjNWQwXHVjMTFjIFx1Yzc3ZFx1Yzc0NCBcdWI1NGMgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgJnF1b3Q7QU5BJnF1b3Q7LCAmcXVvdDsxOTkxJnF1b3Q7LCAmcXVvdDtSQURBUiZxdW90O1x1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE3MFx1Y2U2MCBcdWI0YTQsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWFjMWNcdWIxNTBcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViMGM4XHViMmU0LiBcdWJjMTRcdWI4NWMgJnF1b3Q7XHViZDk5XHVjNzc4XHViNGRjXHViODZjJnF1b3Q7XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmNcdWM3NDAgXHVjMjJiXHVjNzkwXHVjNzc0XHVhY2UwLCBcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YyAyXHVhYzFjXHViOTdjIFx1YmQ5OVx1Yzc3OCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI0NTAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjY2FiIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YjI5NCAwXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMzkzMDIwXHVjNzQwIFx1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YjJlNC4gKFx1YjQ1MCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgMzkzLCAwMjBcdWM3NDQgXHVjNWVjXHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0KSBcdWQ1NThcdWM5YzBcdWI5Y2MsIDIyMlx1YzY0MCAwMTAyMDJcdWIyOTQgXHViZDk5XHVjNzc4XHViNGRjXHViODZjXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1Yzc3NCBcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIDMwXHViZDg0XHVjODE1XHViM2M0IFx1YWNlMFx1YmJmY1x1ZDU1OFx1YjJlNCBcdWJjZjRcdWIyYzgsIDZcdWM3OTBcdWI5YWMgXHViZDk5XHVjNzc4XHViNGRjXHViODZjIFx1YzkxMVx1YzVkMFx1YzExYyAxMjM0NVx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YWM4M1x1Yzc0MCA1NTU1MjUgXHVkNTU4XHViMDk4XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViY2Y0XHViMmU0IFx1YjZmMFx1YzViNFx1YjA5OFx1YjJlNFx1YjI5NCBcdWM4MTBcdWM3NDQgXHVhYzE1XHVjODcwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgTlx1Yzc5MFx1YjlhYyBcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmMgXHVjOTExXHVjNWQwXHVjMTFjIE1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBOXHVjNzkwXHViOWFjIFx1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2YyBcdWM5MTEsIE1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMCwgMSAmbGU7IE0gJmxlOyAxLDAwMCwwMDApIE5cdWM3NDAgXHVjOWRkXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIE5cdWM3OTBcdWI5YWMgXHViZDk5XHVjNzc4XHViNGRjXHViODZjIFx1YzkxMVx1YzVkMFx1YzExYyBNXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzEzMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJJUEFMSU4iLCJkZXNjcmlwdGlvbiI6IjxwPlBlcm8gYW5kIFNsYXZrbyBhcmUgdHdvIHN0dWRlbnRzIHdobyBsb3ZlIG1hdGguIFBlcm8gaXMgdmVyeSBjcmVhdGl2ZSBhbmQgb2Z0ZW4gY29tZXMgdXAgd2l0aCBuZXcgaWRlYXMuIFNsYXZrbyBsYXRlciBzcGVuZHMgZGF5cyB0aGlua2luZyBhYm91dCBQZXJvJiMzOTtzIGlkZWFzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbmUgZGF5IFBlcm8gYW5kIFNsYXZrbyBsZWFybmVkIHdoYXQgYSBwYWxpbmRyb21lIHdhczogYSBzdHJpbmcgcmVhZCB0aGUgc2FtZSBpbiBlaXRoZXIgZGlyZWN0aW9uIChmb3IgZXhhbXBsZSwgJnF1b3Q7QU5BJnF1b3Q7LCAmcXVvdDsxOTkxJnF1b3Q7IGFuZCAmcXVvdDtSQURBUiZxdW90OyBhcmUgcGFsaW5kcm9tZXMpLiBMYXRlciB0aGF0IGRheSBQZXJvIGNhbWUgdXAgd2l0aCBhIG5ldyBjb25jZXB0ICZuZGFzaDsgYSBiaXBhbGluZHJvbWUgKGJpcGFsaW4gZm9yIHNob3J0KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBiaXBhbGluIGlzIGEgbnVtYmVyLCBjb21wb3NlZCBvZiB0d28gcGFsaW5kcm9tZXMgb2YgdGhlIHNhbWUgbGVuZ3RoLiBCb3RoIG9mIHRoZXNlIHBhbGluZHJvbWVzIGFyZSBzdHJpbmdzIG9mIGRlY2ltYWwgZGlnaXRzLCB0aGUgZmlyc3Qgd2hpY2ggbWF5IG5vdCBzdGFydCB3aXRoIHRoZSBkaWdpdCAwICh0aGVyZWZvcmUsIHRoZSBlbnRpcmUgYmlwYWxpbiBtYXkgbm90IHN0YXJ0IHdpdGggYSAwKS4gRm9yIGV4YW1wbGUsIDM5MzAyMCBpcyBhIGJpcGFsaW4gKGNvbXBvc2VkIG9mIHRoZSBwYWxpbmRyb21lcyAzOTMgYW5kIDAyMCksIHdoaWxlIDIyMiBhbmQgMDEwMjAyIGFyZSBub3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIGhlYXJpbmcgYWJvdXQgYmlwYWxpbnMsIFNsYXZrbyBzdGFydGVkIHRoaW5raW5nLiBBZnRlciBoYWxmIGFuIGhvdXIgaGUgZm91bmQgdGhhdCB0aGVyZSBpcyBvbmx5IG9uZSBiaXBhbGluIG9mIGxlbmd0aCA2IHRoYXQgaXMgZGl2aXNpYmxlIGJ5IDEyMzQ1LiBUaGlzIGlzIHRoZSBiaXBhbGluIDU1NTUyNS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2hvY2tlZCBieSB0aGlzIGZpbmRpbmcsIGhlIHdhbnRzIHlvdSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdHdvIGludGVnZXJzIE4gYW5kIE0sIGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgYmlwYWxpbnMgb2YgbGVuZ3RoIE4gdGhhdCBhcmUgZGl2aXNpYmxlIGJ5IE0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMiAmbGU7IE4gJmxlOyAyMCwgMSAmbGU7IE0gJmxlOyAxMDAwMDAwKSwgd2hlcmUgTiBpcyBldmVuLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBiaXBhbGlucyBvZiBsZW5ndGggTiB0aGF0IGFyZSBkaXZpc2libGUgYnkgTS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d