시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 43 8 6 54.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
W3sicHJvYmxlbV9pZCI6IjMxMzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzIxOFx1ZDU1OVx1Yzc0NCBcdWMwYWNcdWI3OTFcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjYzNkXHVjNzU4XHVjODAxXHVjNzc0XHVjNWI0XHVjMTFjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM1NDRcdWM3NzRcdWI1MTRcdWM1YjRcdWI5N2MgXHVjNzk4IFx1YjBiOFx1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YmE4NyBcdWM3N2MgXHViM2Q5XHVjNTQ4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM1NDRcdWM3NzRcdWI1MTRcdWM1YjRcdWI5N2MgXHVjNzc0XHVkNTc0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1YjRcdWIyOTBcdWIwYTAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NDQgXHViYzMwXHVjNmUwXHViMmU0LiBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NDAgXHVjNTVlXHVjNWQwXHVjMTFjIFx1Yzc3ZFx1Yzc0NCBcdWI1NGNcdWM2NDAsIFx1YjRhNFx1YzVkMFx1YzExYyBcdWM3N2RcdWM3NDQgXHViNTRjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsICZxdW90O0FOQSZxdW90OywgJnF1b3Q7MTk5MSZxdW90OywgJnF1b3Q7UkFEQVImcXVvdDtcdWIyOTQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhODdcdWM3N2MgXHViNGE0LCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhYzFjXHViMTUwXHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU3NFx1YjBjOFx1YjJlNC4gXHViYzE0XHViODVjICZxdW90O1x1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2YyZxdW90O1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViZDk5XHVjNzc4XHViNGRjXHViODZjXHVjNzQwIFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YWNlMCwgXHVhYzE5XHVjNzQwIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgMlx1YWMxY1x1Yjk3YyBcdWJkOTlcdWM3NzggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzQgXHViNDUwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Y2NhYiBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWIyOTQgMFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDM5MzAyMFx1Yzc0MCBcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmNcdWM3NzRcdWIyZTQuIChcdWI0NTAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIDM5MywgMDIwXHVjNzQ0IFx1YzVlY1x1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNCkgXHVkNTU4XHVjOWMwXHViOWNjLCAyMjJcdWM2NDAgMDEwMjAyXHViMjk0IFx1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM3NzQgXHViZDk5XHVjNzc4XHViNGRjXHViODZjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyAzMFx1YmQ4NFx1YzgxNVx1YjNjNCBcdWFjZTBcdWJiZmNcdWQ1NThcdWIyZTQgXHViY2Y0XHViMmM4LCA2XHVjNzkwXHViOWFjIFx1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2YyBcdWM5MTFcdWM1ZDBcdWMxMWMgMTIzNDVcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NDAgNTU1NTI1IFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YmNmNFx1YjJlNCBcdWI2ZjBcdWM1YjRcdWIwOThcdWIyZTRcdWIyOTQgXHVjODEwXHVjNzQ0IFx1YWMxNVx1Yzg3MFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIE5cdWM3OTBcdWI5YWMgXHViZDk5XHVjNzc4XHViNGRjXHViODZjIFx1YzkxMVx1YzVkMFx1YzExYyBNXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHROXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgTlx1Yzc5MFx1YjlhYyBcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmMgXHVjOTExLCBNXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMjAsIDEgJmxlOyBNICZsZTsgMSwwMDAsMDAwKSBOXHVjNzQwIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgTlx1Yzc5MFx1YjlhYyBcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmMgXHVjOTExXHVjNWQwXHVjMTFjIE1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzEzMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJJUEFMSU4iLCJkZXNjcmlwdGlvbiI6IjxwPlBlcm8gYW5kIFNsYXZrbyBhcmUgdHdvIHN0dWRlbnRzIHdobyBsb3ZlIG1hdGguIFBlcm8gaXMgdmVyeSBjcmVhdGl2ZSBhbmQgb2Z0ZW4gY29tZXMgdXAgd2l0aCBuZXcgaWRlYXMuIFNsYXZrbyBsYXRlciBzcGVuZHMgZGF5cyB0aGlua2luZyBhYm91dCBQZXJvJiMzOTtzIGlkZWFzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbmUgZGF5IFBlcm8gYW5kIFNsYXZrbyBsZWFybmVkIHdoYXQgYSBwYWxpbmRyb21lIHdhczogYSBzdHJpbmcgcmVhZCB0aGUgc2FtZSBpbiBlaXRoZXIgZGlyZWN0aW9uIChmb3IgZXhhbXBsZSwgJnF1b3Q7QU5BJnF1b3Q7LCAmcXVvdDsxOTkxJnF1b3Q7IGFuZCAmcXVvdDtSQURBUiZxdW90OyBhcmUgcGFsaW5kcm9tZXMpLiBMYXRlciB0aGF0IGRheSBQZXJvIGNhbWUgdXAgd2l0aCBhIG5ldyBjb25jZXB0ICZuZGFzaDsgYSBiaXBhbGluZHJvbWUgKGJpcGFsaW4gZm9yIHNob3J0KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBiaXBhbGluIGlzIGEgbnVtYmVyLCBjb21wb3NlZCBvZiB0d28gcGFsaW5kcm9tZXMgb2YgdGhlIHNhbWUgbGVuZ3RoLiBCb3RoIG9mIHRoZXNlIHBhbGluZHJvbWVzIGFyZSBzdHJpbmdzIG9mIGRlY2ltYWwgZGlnaXRzLCB0aGUgZmlyc3Qgd2hpY2ggbWF5IG5vdCBzdGFydCB3aXRoIHRoZSBkaWdpdCAwICh0aGVyZWZvcmUsIHRoZSBlbnRpcmUgYmlwYWxpbiBtYXkgbm90IHN0YXJ0IHdpdGggYSAwKS4gRm9yIGV4YW1wbGUsIDM5MzAyMCBpcyBhIGJpcGFsaW4gKGNvbXBvc2VkIG9mIHRoZSBwYWxpbmRyb21lcyAzOTMgYW5kIDAyMCksIHdoaWxlIDIyMiBhbmQgMDEwMjAyIGFyZSBub3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIGhlYXJpbmcgYWJvdXQgYmlwYWxpbnMsIFNsYXZrbyBzdGFydGVkIHRoaW5raW5nLiBBZnRlciBoYWxmIGFuIGhvdXIgaGUgZm91bmQgdGhhdCB0aGVyZSBpcyBvbmx5IG9uZSBiaXBhbGluIG9mIGxlbmd0aCA2IHRoYXQgaXMgZGl2aXNpYmxlIGJ5IDEyMzQ1LiBUaGlzIGlzIHRoZSBiaXBhbGluIDU1NTUyNS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2hvY2tlZCBieSB0aGlzIGZpbmRpbmcsIGhlIHdhbnRzIHlvdSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdHdvIGludGVnZXJzIE4gYW5kIE0sIGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgYmlwYWxpbnMgb2YgbGVuZ3RoIE4gdGhhdCBhcmUgZGl2aXNpYmxlIGJ5IE0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMiAmbGU7IE4gJmxlOyAyMCwgMSAmbGU7IE0gJmxlOyAxMDAwMDAwKSwgd2hlcmUgTiBpcyBldmVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgYmlwYWxpbnMgb2YgbGVuZ3RoIE4gdGhhdCBhcmUgZGl2aXNpYmxlIGJ5IE0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==