시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 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
W3sicHJvYmxlbV9pZCI6IjMxMzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzIxOFx1ZDU1OVx1Yzc0NCBcdWMwYWNcdWI3OTFcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjYzNkXHVjNzU4XHVjODAxXHVjNzc0XHVjNWI0XHVjMTFjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM1NDRcdWM3NzRcdWI1MTRcdWM1YjRcdWI5N2MgXHVjNzk4IFx1YjBiOFx1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YmE3MFx1Y2U2MCBcdWIzZDlcdWM1NDggXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzU0NFx1Yzc3NFx1YjUxNFx1YzViNFx1Yjk3YyBcdWM3NzRcdWQ1NzRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzViNFx1YjI5MFx1YjBhMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0NCBcdWJjMzBcdWM2ZTBcdWIyZTQuIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0MCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHVjNzdkXHVjNzQ0IFx1YjU0Y1x1YzY0MCwgXHViNGE0XHVjNWQwXHVjMTFjIFx1Yzc3ZFx1Yzc0NCBcdWI1NGMgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgJnF1b3Q7QU5BJnF1b3Q7LCAmcXVvdDsxOTkxJnF1b3Q7LCAmcXVvdDtSQURBUiZxdW90O1x1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmE3MFx1Y2U2MCBcdWI0YTQsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWFjMWNcdWIxNTBcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViMGM4XHViMmU0LiBcdWJjMTRcdWI4NWMgJnF1b3Q7XHViZDk5XHVjNzc4XHViNGRjXHViODZjJnF1b3Q7XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmNcdWM3NDAgXHVjMjJiXHVjNzkwXHVjNzc0XHVhY2UwLCBcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YyAyXHVhYzFjXHViOTdjIFx1YmQ5OVx1Yzc3OCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI0NTAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjY2FiIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YjI5NCAwXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMzkzMDIwXHVjNzQwIFx1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YjJlNC4gKFx1YjQ1MCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgMzkzLCAwMjBcdWM3NDQgXHVjNWVjXHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0KSBcdWQ1NThcdWM5YzBcdWI5Y2MsIDIyMlx1YzY0MCAwMTAyMDJcdWIyOTQgXHViZDk5XHVjNzc4XHViNGRjXHViODZjXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1Yzc3NCBcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIDMwXHViZDg0XHVjODE1XHViM2M0IFx1YWNlMFx1YmJmY1x1ZDU1OFx1YjJlNCBcdWJjZjRcdWIyYzgsIDZcdWM3OTBcdWI5YWMgXHViZDk5XHVjNzc4XHViNGRjXHViODZjIFx1YzkxMVx1YzVkMFx1YzExYyAxMjM0NVx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YWM4M1x1Yzc0MCA1NTU1MjUgXHVkNTU4XHViMDk4XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViY2Y0XHViMmU0IFx1YjZmMFx1YzViNFx1YjA5OFx1YjJlNFx1YjI5NCBcdWM4MTBcdWM3NDQgXHVhYzE1XHVjODcwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgTlx1Yzc5MFx1YjlhYyBcdWJkOTlcdWM3NzhcdWI0ZGNcdWI4NmMgXHVjOTExXHVjNWQwXHVjMTFjIE1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBOXHVjNzkwXHViOWFjIFx1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2YyBcdWM5MTEsIE1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMCwgMSAmbGU7IE0gJmxlOyAxLDAwMCwwMDApIE5cdWM3NDAgXHVjOWRkXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBOXHVjNzkwXHViOWFjIFx1YmQ5OVx1Yzc3OFx1YjRkY1x1Yjg2YyBcdWM5MTFcdWM1ZDBcdWMxMWMgTVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQklQQUxJTiIsImRlc2NyaXB0aW9uIjoiPHA+UGVybyBhbmQgU2xhdmtvIGFyZSB0d28gc3R1ZGVudHMgd2hvIGxvdmUgbWF0aC4gUGVybyBpcyB2ZXJ5IGNyZWF0aXZlIGFuZCBvZnRlbiBjb21lcyB1cCB3aXRoIG5ldyBpZGVhcy4gU2xhdmtvIGxhdGVyIHNwZW5kcyBkYXlzIHRoaW5raW5nIGFib3V0IFBlcm8mIzM5O3MgaWRlYXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uZSBkYXkgUGVybyBhbmQgU2xhdmtvIGxlYXJuZWQgd2hhdCBhIHBhbGluZHJvbWUgd2FzOiBhIHN0cmluZyByZWFkIHRoZSBzYW1lIGluIGVpdGhlciBkaXJlY3Rpb24gKGZvciBleGFtcGxlLCAmcXVvdDtBTkEmcXVvdDssICZxdW90OzE5OTEmcXVvdDsgYW5kICZxdW90O1JBREFSJnF1b3Q7IGFyZSBwYWxpbmRyb21lcykuIExhdGVyIHRoYXQgZGF5IFBlcm8gY2FtZSB1cCB3aXRoIGEgbmV3IGNvbmNlcHQgJm5kYXNoOyBhIGJpcGFsaW5kcm9tZSAoYmlwYWxpbiBmb3Igc2hvcnQpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIGJpcGFsaW4gaXMgYSBudW1iZXIsIGNvbXBvc2VkIG9mIHR3byBwYWxpbmRyb21lcyBvZiB0aGUgc2FtZSBsZW5ndGguIEJvdGggb2YgdGhlc2UgcGFsaW5kcm9tZXMgYXJlIHN0cmluZ3Mgb2YgZGVjaW1hbCBkaWdpdHMsIHRoZSBmaXJzdCB3aGljaCBtYXkgbm90IHN0YXJ0IHdpdGggdGhlIGRpZ2l0IDAgKHRoZXJlZm9yZSwgdGhlIGVudGlyZSBiaXBhbGluIG1heSBub3Qgc3RhcnQgd2l0aCBhIDApLiBGb3IgZXhhbXBsZSwgMzkzMDIwIGlzIGEgYmlwYWxpbiAoY29tcG9zZWQgb2YgdGhlIHBhbGluZHJvbWVzIDM5MyBhbmQgMDIwKSwgd2hpbGUgMjIyIGFuZCAwMTAyMDIgYXJlIG5vdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgaGVhcmluZyBhYm91dCBiaXBhbGlucywgU2xhdmtvIHN0YXJ0ZWQgdGhpbmtpbmcuIEFmdGVyIGhhbGYgYW4gaG91ciBoZSBmb3VuZCB0aGF0IHRoZXJlIGlzIG9ubHkgb25lIGJpcGFsaW4gb2YgbGVuZ3RoIDYgdGhhdCBpcyBkaXZpc2libGUgYnkgMTIzNDUuIFRoaXMgaXMgdGhlIGJpcGFsaW4gNTU1NTI1LiZuYnNwOzxcL3A+XHJcblxyXG48cD5TaG9ja2VkIGJ5IHRoaXMgZmluZGluZywgaGUgd2FudHMgeW91IHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0d28gaW50ZWdlcnMgTiBhbmQgTSwgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBiaXBhbGlucyBvZiBsZW5ndGggTiB0aGF0IGFyZSBkaXZpc2libGUgYnkgTS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VycyBOIGFuZCBNICgyICZsZTsgTiAmbGU7IDIwLCAxICZsZTsgTSAmbGU7IDEwMDAwMDApLCB3aGVyZSBOIGlzIGV2ZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBiaXBhbGlucyBvZiBsZW5ndGggTiB0aGF0IGFyZSBkaXZpc2libGUgYnkgTS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d