시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 15265 2741 2049 19.198%

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

  • 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
  • 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
  • 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
  • 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
  • 상근: 얼마나 많은데?
  • 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 5000자리 이하의 암호가 주어진다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

예제 입력 1

25114

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIwMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzhcdWNmNTRcdWI0ZGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWIwYThcdWI5ZTRcdWFjMDRcdWM3NTggXHViMzAwXHVkNjU0XHViOTdjIFx1YjRlM1x1YjI5NCBcdWFjODNcdWM3NDQgXHViYzI5XHVjOWMwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWIzMDBcdWQ2NTRcdWI5N2MgXHVjMTFjXHViODVjIFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWIzMDBcdWQ2NTRcdWI5N2MgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzBjMVx1YWRmYzogXHVhZGY4XHViMGU1IFx1YWMwNFx1YjJlOFx1ZDc4OCBcdWM1NTRcdWQ2MzhcdWQ2NTQgXHVkNTU4XHVjNzkwLiBBXHViOTdjIDFcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwLCBCXHViMjk0IDJcdWI4NWMsIFx1YWRmOFx1YjlhY1x1YWNlMCBaXHViMjk0IDI2XHVjNzNjXHViODVjIFx1ZDU1OFx1YjI5NFx1YWM3MFx1YzU3Yy48XC9saT5cclxuXHQ8bGk+XHVjMTIwXHVjNjAxOiBcdWFkZjhcdWI3ZmMgXHVjNTQ4XHViM2ZjLiBcdWI5Y2NcdWM1N2QsICZxdW90O0JFQU4mcXVvdDtcdWM3NDQgXHVjNTU0XHVkNjM4XHVkNjU0XHVkNTU4XHViYTc0IDI1MTE0XHVhYzAwIFx1YjA5OFx1YzYyNFx1YjI5NFx1YjM3MCwgXHVjNzc0XHVhYzc4IFx1YjJlNFx1YzJkYyBcdWFlMDBcdWM3OTBcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YzViNC48XC9saT5cclxuXHQ8bGk+XHVjMGMxXHVhZGZjOiBcdWFkZjhcdWI4MDdcdWIxMjQuIDI1MTE0XHViOTdjIFx1YjJlNFx1YzJkYyBcdWM2MDFcdWM1YjRcdWI4NWMgXHViYzE0XHVhZmI4XHViYTc0LCAmcXVvdDtCRUFBRCZxdW90OywgJnF1b3Q7WUFBRCZxdW90OywgJnF1b3Q7WUFOJnF1b3Q7LCAmcXVvdDtZS0QmcXVvdDssICZxdW90O0JFS0QmcXVvdDssICZxdW90O0JFQU4mcXVvdDsgXHVjZDFkIDZcdWFjMDBcdWM5YzBcdWFjMDAgXHViMDk4XHVjNjI0XHViMjk0XHViMzcwLCBCRUFOXHVjNzc0IFx1YjlkZVx1YjI5NCBcdWIyZThcdWM1YjRcdWI3N2NcdWIyOTRcdWFjNzQgXHVjMjdkXHVhYzhjIFx1YzU0Y1x1YzIxOCBcdWM3ODhcdWM3OTZcdWM1NDQ/PFwvbGk+XHJcblx0PGxpPlx1YzEyMFx1YzYwMTogXHVjNjA4XHVhYzAwIFx1YzgwMVx1YzgwOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWIxMjQgXHUzMTYwXHUzMTYwIFx1YjljY1x1YzU3ZCBcdWIwYjRcdWFjMDAgNTAwXHVjNzkwXHViOWFjIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWM1NTRcdWQ2MzhcdWQ2NTQgXHVkNTg4XHViMmU0XHVhY2UwIFx1ZDU3NFx1YmQxMC4gXHVhZGY4IFx1YjU0Y1x1YjI5NCBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NzRcdWMxMWRcdWM3NzQgXHVjODE1XHViOWQwIFx1YjljZVx1Yzc0MFx1YjM3MCwgXHVhZGY4XHVhYzc4IFx1YzViOFx1YzgxYyBcdWIyZTRcdWQ1NzRcdWJkMTA/PFwvbGk+XHJcblx0PGxpPlx1YzBjMVx1YWRmYzogXHVjNWJjXHViOWM4XHViMDk4IFx1YjljZVx1Yzc0MFx1YjM3MD88XC9saT5cclxuXHQ8bGk+XHVjMTIwXHVjNjAxOiBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAhPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzU1NFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjNTU0XHVkNjM4XHVjNzU4IFx1ZDU3NFx1YzExZFx1Yzc3NCBcdWJhODcgXHVhYzAwXHVjOWMwXHVhYzAwIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA1MDAwXHVjNzkwXHViOWFjIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1NTRcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDU3NFx1YzExZFx1Yzc1OCBcdWFjMDBcdWM5ZDNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4MTVcdWIyZjVcdWM3NzQgXHViOWU0XHVjNmIwIFx1ZDA3NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjLCAxMDAwMDAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NTRcdWQ2MzhcdWFjMDAgXHVjNzk4XHViYWJiXHViNDE4XHVjNWI0IFx1YzU1NFx1ZDYzOFx1Yjk3YyBcdWQ1NzRcdWMxMWRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFscGhhY29kZSIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2UgYW5kIEJvYiBuZWVkIHRvIHNlbmQgc2VjcmV0IG1lc3NhZ2VzIHRvIGVhY2ggb3RoZXIgYW5kIGFyZSBkaXNjdXNzaW5nIHdheXMgdG8gZW5jb2RlIHRoZWlyIG1lc3NhZ2VzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkFsaWNlOiAmbGRxdW87TGV0JnJzcXVvO3MganVzdCB1c2UgYSB2ZXJ5IHNpbXBsZSBjb2RlOiBXZSZyc3F1bztsbCBhc3NpZ24gJmxzcXVvO0EmcnNxdW87IHRoZSBjb2RlIHdvcmQgMSwgJmxzcXVvO0ImcnNxdW87IHdpbGwgYmUgMiwgYW5kIHNvIG9uIGRvd24gdG8gJmxzcXVvO1omcnNxdW87IGJlaW5nIGFzc2lnbmVkIDI2LiZyZHF1bzs8XC9saT5cclxuXHQ8bGk+Qm9iOiAmbGRxdW87VGhhdCZyc3F1bztzIGEgc3R1cGlkIGNvZGUsIEFsaWNlLiBTdXBwb3NlIEkgc2VuZCB5b3UgdGhlIHdvcmQgJmxzcXVvO0JFQU4mcnNxdW87IGVuY29kZWQgYXMgMjUxMTQuIFlvdSBjb3VsZCBkZWNvZGUgdGhhdCBpbiBtYW55IGRpZmZlcmVudCB3YXlzISZyZHF1bzs8XC9saT5cclxuXHQ8bGk+QWxpY2U6ICZsZHF1bztTdXJlIHlvdSBjb3VsZCwgYnV0IHdoYXQgd29yZHMgd291bGQgeW91IGdldD8gT3RoZXIgdGhhbiAmbHNxdW87QkVBTiZyc3F1bzssIHlvdSZyc3F1bztkIGdldCAmbHNxdW87QkVBQUQmcnNxdW87LCAmbHNxdW87WUFBRCZyc3F1bzssICZsc3F1bztZQU4mcnNxdW87LCAmbHNxdW87WUtEJnJzcXVvOyBhbmQgJmxzcXVvO0JFS0QmcnNxdW87LiBJIHRoaW5rIHlvdSB3b3VsZCBiZSBhYmxlIHRvIGZpZ3VyZSBvdXQgdGhlIGNvcnJlY3QgZGVjb2RpbmcuIEFuZCB3aHkgd291bGQgeW91IHNlbmQgbWUgdGhlIHdvcmQgJmxzcXVvO0JFQU4mcnNxdW87IGFueXdheT8mcmRxdW87PFwvbGk+XHJcblx0PGxpPkJvYjogJmxkcXVvO09LLCBtYXliZSB0aGF0JnJzcXVvO3MgYSBiYWQgZXhhbXBsZSwgYnV0IEkgYmV0IHlvdSB0aGF0IGlmIHlvdSBnb3QgYSBzdHJpbmcgb2YgbGVuZ3RoIDUwMCB0aGVyZSB3b3VsZCBiZSB0b25zIG9mIGRpZmZlcmVudCBkZWNvZGluZ3MgYW5kIHdpdGggdGhhdCBtYW55IHlvdSB3b3VsZCBmaW5kIGF0IGxlYXN0IHR3byBkaWZmZXJlbnQgb25lcyB0aGF0IHdvdWxkIG1ha2Ugc2Vuc2UuJnJkcXVvOzxcL2xpPlxyXG5cdDxsaT5BbGljZTogJmxkcXVvO0hvdyBtYW55IGRpZmZlcmVudCBkZWNvZGluZ3M/JnJkcXVvOzxcL2xpPlxyXG5cdDxsaT5Cb2I6ICZsZHF1bztKaWxsaW9ucyEmcmRxdW87PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIHNvbWUgcmVhc29uLCBBbGljZSBpcyBzdGlsbCB1bmNvbnZpbmNlZCBieSBCb2ImcnNxdW87cyBhcmd1bWVudCwgc28gc2hlIHJlcXVpcmVzIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIGhvdyBtYW55IGRlY29kaW5ncyB0aGVyZSBjYW4gYmUgZm9yIGEgZ2l2ZW4gc3RyaW5nIHVzaW5nIGhlciBjb2RlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIG11bHRpcGxlIGlucHV0IHNldHMuIEVhY2ggc2V0IHdpbGwgY29uc2lzdCBvZiBhIHNpbmdsZSBsaW5lIG9mIGRpZ2l0cyByZXByZXNlbnRpbmcgYSB2YWxpZCBlbmNyeXB0aW9uIChmb3IgZXhhbXBsZSwgbm8gbGluZSB3aWxsIGJlZ2luIHdpdGggYSAwKS4gVGhlcmUgd2lsbCBiZSBubyBzcGFjZXMgYmV0d2VlbiB0aGUgZGlnaXRzLiBBbiBpbnB1dCBsaW5lIG9mICZsc3F1bzswJnJzcXVvOyB3aWxsIHRlcm1pbmF0ZSB0aGUgaW5wdXQgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgc2V0LCBvdXRwdXQgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBkZWNvZGluZ3MgZm9yIHRoZSBpbnB1dCBzdHJpbmcuIEFsbCBhbnN3ZXJzIHdpbGwgYmUgd2l0aGluIHRoZSByYW5nZSBvZiBhIGxvbmcgdmFyaWFibGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > North America > East Central North America Regional > 2004 East Central Regional Contest A번