시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5495410894798420.369%

문제

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

  • 상근: 그냥 간단히 암호화 하자. 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

예제 입력 2

1111111111

예제 출력 2

89
W3sicHJvYmxlbV9pZCI6IjIwMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzhcdWNmNTRcdWI0ZGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWIwYThcdWI5ZTRcdWFjMDRcdWM3NTggXHViMzAwXHVkNjU0XHViOTdjIFx1YjRlM1x1YjI5NCBcdWFjODNcdWM3NDQgXHViYzI5XHVjOWMwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWIzMDBcdWQ2NTRcdWI5N2MgXHVjMTFjXHViODVjIFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWIzMDBcdWQ2NTRcdWI5N2MgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzBjMVx1YWRmYzogXHVhZGY4XHViMGU1IFx1YWMwNFx1YjJlOFx1ZDc4OCBcdWM1NTRcdWQ2MzhcdWQ2NTQgXHVkNTU4XHVjNzkwLiBBXHViOTdjIDFcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwLCBCXHViMjk0IDJcdWI4NWMsIFx1YWRmOFx1YjlhY1x1YWNlMCBaXHViMjk0IDI2XHVjNzNjXHViODVjIFx1ZDU1OFx1YjI5NFx1YWM3MFx1YzU3Yy48XC9saT5cclxuXHQ8bGk+XHVjMTIwXHVjNjAxOiBcdWFkZjhcdWI3ZmMgXHVjNTQ4XHViM2ZjLiBcdWI5Y2NcdWM1N2QsICZxdW90O0JFQU4mcXVvdDtcdWM3NDQgXHVjNTU0XHVkNjM4XHVkNjU0XHVkNTU4XHViYTc0IDI1MTE0XHVhYzAwIFx1YjA5OFx1YzYyNFx1YjI5NFx1YjM3MCwgXHVjNzc0XHVhYzc4IFx1YjJlNFx1YzJkYyBcdWFlMDBcdWM3OTBcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YzViNC48XC9saT5cclxuXHQ8bGk+XHVjMGMxXHVhZGZjOiBcdWFkZjhcdWI4MDdcdWIxMjQuIDI1MTE0XHViOTdjIFx1YjJlNFx1YzJkYyBcdWM2MDFcdWM1YjRcdWI4NWMgXHViYzE0XHVhZmI4XHViYTc0LCAmcXVvdDtCRUFBRCZxdW90OywgJnF1b3Q7WUFBRCZxdW90OywgJnF1b3Q7WUFOJnF1b3Q7LCAmcXVvdDtZS0QmcXVvdDssICZxdW90O0JFS0QmcXVvdDssICZxdW90O0JFQU4mcXVvdDsgXHVjZDFkIDZcdWFjMDBcdWM5YzBcdWFjMDAgXHViMDk4XHVjNjI0XHViMjk0XHViMzcwLCBCRUFOXHVjNzc0IFx1YjlkZVx1YjI5NCBcdWIyZThcdWM1YjRcdWI3N2NcdWIyOTRcdWFjNzQgXHVjMjdkXHVhYzhjIFx1YzU0Y1x1YzIxOCBcdWM3ODhcdWM3OTZcdWM1NDQ/PFwvbGk+XHJcblx0PGxpPlx1YzEyMFx1YzYwMTogXHVjNjA4XHVhYzAwIFx1YzgwMVx1YzgwOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWIxMjQgXHUzMTYwXHUzMTYwIFx1YjljY1x1YzU3ZCBcdWIwYjRcdWFjMDAgNTAwXHVjNzkwXHViOWFjIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWM1NTRcdWQ2MzhcdWQ2NTQgXHVkNTg4XHViMmU0XHVhY2UwIFx1ZDU3NFx1YmQxMC4gXHVhZGY4IFx1YjU0Y1x1YjI5NCBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NzRcdWMxMWRcdWM3NzQgXHVjODE1XHViOWQwIFx1YjljZVx1Yzc0MFx1YjM3MCwgXHVhZGY4XHVhYzc4IFx1YzViOFx1YzgxYyBcdWIyZTRcdWQ1NzRcdWJkMTA/PFwvbGk+XHJcblx0PGxpPlx1YzBjMVx1YWRmYzogXHVjNWJjXHViOWM4XHViMDk4IFx1YjljZVx1Yzc0MFx1YjM3MD88XC9saT5cclxuXHQ8bGk+XHVjMTIwXHVjNjAxOiBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAhPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzU1NFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjNTU0XHVkNjM4XHVjNzU4IFx1ZDU3NFx1YzExZFx1Yzc3NCBcdWJhODcgXHVhYzAwXHVjOWMwXHVhYzAwIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA1MDAwXHVjNzkwXHViOWFjIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1NTRcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1NTRcdWQ2MzhcdWIyOTQgXHVjMjJiXHVjNzkwXHViODVjJm5ic3A7XHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NzRcdWMxMWRcdWM3NTggXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjODE1XHViMmY1XHVjNzc0IFx1YjllNFx1YzZiMCBcdWQwNzQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YywgMTAwMDAwMFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTU0XHVkNjM4XHVhYzAwIFx1Yzc5OFx1YmFiYlx1YjQxOFx1YzViNCBcdWM1NTRcdWQ2MzhcdWI5N2MgXHVkNTc0XHVjMTFkXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIwMTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbHBoYWNvZGUiLCJkZXNjcmlwdGlvbiI6IjxwPkFsaWNlIGFuZCBCb2IgbmVlZCB0byBzZW5kIHNlY3JldCBtZXNzYWdlcyB0byBlYWNoIG90aGVyIGFuZCBhcmUgZGlzY3Vzc2luZyB3YXlzIHRvIGVuY29kZSB0aGVpciBtZXNzYWdlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BbGljZTogJmxkcXVvO0xldCZyc3F1bztzIGp1c3QgdXNlIGEgdmVyeSBzaW1wbGUgY29kZTogV2UmcnNxdW87bGwgYXNzaWduICZsc3F1bztBJnJzcXVvOyB0aGUgY29kZSB3b3JkIDEsICZsc3F1bztCJnJzcXVvOyB3aWxsIGJlIDIsIGFuZCBzbyBvbiBkb3duIHRvICZsc3F1bztaJnJzcXVvOyBiZWluZyBhc3NpZ25lZCAyNi4mcmRxdW87PFwvbGk+XHJcblx0PGxpPkJvYjogJmxkcXVvO1RoYXQmcnNxdW87cyBhIHN0dXBpZCBjb2RlLCBBbGljZS4gU3VwcG9zZSBJIHNlbmQgeW91IHRoZSB3b3JkICZsc3F1bztCRUFOJnJzcXVvOyBlbmNvZGVkIGFzIDI1MTE0LiBZb3UgY291bGQgZGVjb2RlIHRoYXQgaW4gbWFueSBkaWZmZXJlbnQgd2F5cyEmcmRxdW87PFwvbGk+XHJcblx0PGxpPkFsaWNlOiAmbGRxdW87U3VyZSB5b3UgY291bGQsIGJ1dCB3aGF0IHdvcmRzIHdvdWxkIHlvdSBnZXQ/IE90aGVyIHRoYW4gJmxzcXVvO0JFQU4mcnNxdW87LCB5b3UmcnNxdW87ZCBnZXQgJmxzcXVvO0JFQUFEJnJzcXVvOywgJmxzcXVvO1lBQUQmcnNxdW87LCAmbHNxdW87WUFOJnJzcXVvOywgJmxzcXVvO1lLRCZyc3F1bzsgYW5kICZsc3F1bztCRUtEJnJzcXVvOy4gSSB0aGluayB5b3Ugd291bGQgYmUgYWJsZSB0byBmaWd1cmUgb3V0IHRoZSBjb3JyZWN0IGRlY29kaW5nLiBBbmQgd2h5IHdvdWxkIHlvdSBzZW5kIG1lIHRoZSB3b3JkICZsc3F1bztCRUFOJnJzcXVvOyBhbnl3YXk/JnJkcXVvOzxcL2xpPlxyXG5cdDxsaT5Cb2I6ICZsZHF1bztPSywgbWF5YmUgdGhhdCZyc3F1bztzIGEgYmFkIGV4YW1wbGUsIGJ1dCBJIGJldCB5b3UgdGhhdCBpZiB5b3UgZ290IGEgc3RyaW5nIG9mIGxlbmd0aCA1MDAgdGhlcmUgd291bGQgYmUgdG9ucyBvZiBkaWZmZXJlbnQgZGVjb2RpbmdzIGFuZCB3aXRoIHRoYXQgbWFueSB5b3Ugd291bGQgZmluZCBhdCBsZWFzdCB0d28gZGlmZmVyZW50IG9uZXMgdGhhdCB3b3VsZCBtYWtlIHNlbnNlLiZyZHF1bzs8XC9saT5cclxuXHQ8bGk+QWxpY2U6ICZsZHF1bztIb3cgbWFueSBkaWZmZXJlbnQgZGVjb2RpbmdzPyZyZHF1bzs8XC9saT5cclxuXHQ8bGk+Qm9iOiAmbGRxdW87SmlsbGlvbnMhJnJkcXVvOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBzb21lIHJlYXNvbiwgQWxpY2UgaXMgc3RpbGwgdW5jb252aW5jZWQgYnkgQm9iJnJzcXVvO3MgYXJndW1lbnQsIHNvIHNoZSByZXF1aXJlcyBhIHByb2dyYW0gdGhhdCB3aWxsIGRldGVybWluZSBob3cgbWFueSBkZWNvZGluZ3MgdGhlcmUgY2FuIGJlIGZvciBhIGdpdmVuIHN0cmluZyB1c2luZyBoZXIgY29kZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBtdWx0aXBsZSBpbnB1dCBzZXRzLiBFYWNoIHNldCB3aWxsIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSBvZiBkaWdpdHMgcmVwcmVzZW50aW5nIGEgdmFsaWQgZW5jcnlwdGlvbiAoZm9yIGV4YW1wbGUsIG5vIGxpbmUgd2lsbCBiZWdpbiB3aXRoIGEgMCkuIFRoZXJlIHdpbGwgYmUgbm8gc3BhY2VzIGJldHdlZW4gdGhlIGRpZ2l0cy4gQW4gaW5wdXQgbGluZSBvZiAmbHNxdW87MCZyc3F1bzsgd2lsbCB0ZXJtaW5hdGUgdGhlIGlucHV0IGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IHNldCwgb3V0cHV0IHRoZSBudW1iZXIgb2YgcG9zc2libGUgZGVjb2RpbmdzIGZvciB0aGUgaW5wdXQgc3RyaW5nLiBBbGwgYW5zd2VycyB3aWxsIGJlIHdpdGhpbiB0aGUgcmFuZ2Ugb2YgYSBsb25nIHZhcmlhYmxlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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