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

문제

내일이면 대한민국에 새로운 대통령이 취임하게 된다. 새로운 정부는, 아래와 같이 19자리로 된 새로운 주민등록번호 체계를 도입한다고 한다.

DDMMYYYYAAAAAAAAAAC

YYYY는 생년, MM은 생월, DD는 생일을 의미한다. 생년은 0001 이상 9999 이하의 수가 되며, MM은 01 이상 12 이하, DD는 01 이상 31 이하이다. 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지이며, 2월은 평년은 28일까지, 윤년은 29일까지이다. 윤년이란 YYYY가 (1) 100의 배수를 제외한 4의 배수이거나 (2) 400의 배수인 경우가 해당된다.

A로 된 10자리는 어떤 숫자라도 올 수 있다. 마지막 자리인 C는 CONTROL-DIGIT으로, 아래와 같은 알고리즘에 의해 생성된다.

  1. C를 제외한 주민등록번호상의 18자리의 수를 순서대로 Z1, Z2, …, Z18이라고 하자.
  2. S = (10×Z1 + 9×Z2 + 8×Z3 + … + 2×Z9 + 10×Z10 + 9×Z11 + 8×Z12 + … + 2×Z18) % 19
  3. S가 9 이하이면 C=S, 아니면 C = 19 - S

이러한 새로운 주민등록번호 체계상의 한 주민등록번호의 일부 숫자가 지워져 있다. 위의 조건을 만족시키는 가능한 모든 주민등록번호의 경우의 수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 19자리의 주민등록번호가 주어진다. 숫자 또는 X로 주어지게 되는데 X는 숫자가 지워졌음을 의미한다.

출력

첫째 줄에 조건을 만족시키는 가능한 모든 주민등록번호의 경우의 수를 출력한다. 답은 항상 263보다 작다.

예제 입력 1

XX0220051234567890X

예제 출력 1

28

예제 입력 2

XXXX200577XXXXXXX7X

예제 출력 2

3650000000

예제 입력 3

0XX52X0512X456X8903

예제 출력 3

946
W3sicHJvYmxlbV9pZCI6IjE2NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjBiNFx1Yzc3Y1x1Yzc3NFx1YmE3NCBcdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmRcdWM1ZDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YjMwMFx1ZDFiNVx1YjgzOVx1Yzc3NCBcdWNkZThcdWM3ODRcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjODE1XHViZDgwXHViMjk0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDE5XHVjNzkwXHViOWFjXHViODVjIFx1YjQxYyBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjOGZjXHViYmZjXHViNGYxXHViODVkXHViYzg4XHVkNjM4IFx1Y2NiNFx1YWNjNFx1Yjk3YyBcdWIzYzRcdWM3ODVcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5ERE1NWVlZWUFBQUFBQUFBQUFDPFwvcD5cclxuXHJcbjxwPllZWVlcdWIyOTQgXHVjMGRkXHViMTQ0LCBNTVx1Yzc0MCBcdWMwZGRcdWM2ZDQsIEREXHViMjk0IFx1YzBkZFx1Yzc3Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzBkZFx1YjE0NFx1Yzc0MCAwMDAxIFx1Yzc3NFx1YzBjMSA5OTk5IFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWMyMThcdWFjMDAgXHViNDE4XHViYTcwLCBNTVx1Yzc0MCAwMSBcdWM3NzRcdWMwYzEgMTIgXHVjNzc0XHVkNTU4LCBERFx1YjI5NCAwMSBcdWM3NzRcdWMwYzEgMzEgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiAxLCAzLCA1LCA3LCA4LCAxMCwgMTJcdWM2ZDRcdWM3NDAgMzFcdWM3N2NcdWFlNGNcdWM5YzAsIDQsIDYsIDksIDExXHVjNmQ0XHVjNzQwIDMwXHVjNzdjXHVhZTRjXHVjOWMwXHVjNzc0XHViYTcwLCAyXHVjNmQ0XHVjNzQwIFx1ZDNjOVx1YjE0NFx1Yzc0MCAyOFx1Yzc3Y1x1YWU0Y1x1YzljMCwgXHVjNzI0XHViMTQ0XHVjNzQwIDI5XHVjNzdjXHVhZTRjXHVjOWMwXHVjNzc0XHViMmU0LiBcdWM3MjRcdWIxNDRcdWM3NzRcdWI3ODAgWVlZWVx1YWMwMCAoMSkgMTAwXHVjNzU4IFx1YmMzMFx1YzIxOFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgNFx1Yzc1OCBcdWJjMzBcdWMyMThcdWM3NzRcdWFjNzBcdWIwOTggKDIpIDQwMFx1Yzc1OCBcdWJjMzBcdWMyMThcdWM3NzggXHVhY2JkXHVjNmIwXHVhYzAwIFx1ZDU3NFx1YjJmOVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+QVx1Yjg1YyBcdWI0MWMgMTBcdWM3OTBcdWI5YWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzIyYlx1Yzc5MFx1Yjc3Y1x1YjNjNCBcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1Yzc5MFx1YjlhY1x1Yzc3OCBDXHViMjk0IENPTlRST0wtRElHSVRcdWM3M2NcdWI4NWMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWMwZGRcdWMxMzFcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Q1x1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHVjOGZjXHViYmZjXHViNGYxXHViODVkXHViYzg4XHVkNjM4XHVjMGMxXHVjNzU4IDE4XHVjNzkwXHViOWFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgWjEsIFoyLCAmaGVsbGlwOywgWjE4XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9saT5cclxuXHQ8bGk+UyA9ICgxMCZ0aW1lcztaMSArIDkmdGltZXM7WjIgKyA4JnRpbWVzO1ozICsgJmhlbGxpcDsgKyAyJnRpbWVzO1o5ICsgMTAmdGltZXM7WjEwICsgOSZ0aW1lcztaMTEgKyA4JnRpbWVzO1oxMiArICZoZWxsaXA7ICsgMiZ0aW1lcztaMTgpICUgMTk8XC9saT5cclxuXHQ8bGk+U1x1YWMwMCA5IFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YmE3NCBDPVMsIFx1YzU0NFx1YjJjOFx1YmE3NCBDID0gMTkgLSBTPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzggXHVjY2I0XHVhY2M0XHVjMGMxXHVjNzU4IFx1ZDU1YyBcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzhcdWM3NTggXHVjNzdjXHViZDgwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzhmY1x1YmJmY1x1YjRmMVx1Yjg1ZFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YzEzOFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAxOVx1Yzc5MFx1YjlhY1x1Yzc1OCBcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMmJcdWM3OTAgXHViNjEwXHViMjk0IFhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxOFx1YjI5NFx1YjM3MCBYXHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM4NGNcdWM3NGNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzhmY1x1YmJmY1x1YjRmMVx1Yjg1ZFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSAyPHN1cD42MzxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE2NjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJqbWJnIiwiZGVzY3JpcHRpb24iOiI8cD5FdmVyeSBjaXRpemVuIGluIG9uZSBjb3VudHJ5IGhhcyBoaXMgb3duIGlkZW50aWZpY2F0aW9uIG51bWJlciBjb25zaXN0aW5nIG9mIDE5IGRpZ2l0cyBpbiB0aGUgZm9ybWF0OiZuYnNwOzxcL3A+XHJcblxyXG48cD5ERE1NWVlZWUFBQUFBQUFBQUFDJm5ic3A7PFwvcD5cclxuXHJcbjxwPndoZXJlIGRpZ2l0cyBERCBkZW5vdGUgZGF5LCBNTSBtb250aCwgYW5kIFlZWVkgeWVhciBvZiB0aGUgYmlydGguJm5ic3A7PFwvcD5cclxuXHJcbjxwPlllYXIgb2YgYmlydGggaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIGJldHdlZW4gMDAwMSBhbmQgOTk5OSBpbmNsdXNpdmUuIFllYXIgaXMgYSBsZWFwIHllYXIgaWYgaXQgaXMgZGl2aXNpYmxlIGJ5IDQsIGJ1dCBub3QgYnkgMTAwIG9yIGlmIGl0IGlzIGRpdmlzaWJsZSBieSA0MDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRpZ2l0cyBkZW5vdGVkIGJ5IEEgY2FuIGJlIGFyYml0cmFyeSwgYW5kIEMgaXMgYSBjb250cm9sLWRpZ2l0IGNhbGN1bGF0ZWQgYnkgdGhlIGZvbGxvd2luZyBhbGdvcml0aG06Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+RGVub3RlIGFsbCB0aGUgZGlnaXRzIGluIGlkZW50aWZpY2F0aW9uIG51bWJlciwgZXhjZXB0IHRoZSBsYXN0IG9uZSwgd2l0aCBaMS4uLloxOCZuYnNwOzxcL2xpPlxyXG5cdDxsaT5TID0gKDEwKloxKzkqWjIrOCpaMysgLi4uICsyKlo5KzEwKloxMCs5KloxMSs4KloxMisgLi4uICsyKloxOCkgbW9kIDE5Jm5ic3A7PFwvbGk+XHJcblx0PGxpPmlmIFMgJmxlOyA5IHRoZW4gQyA9IFMsIG90aGVyd2lzZSBDID0gMTktUyZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkEgZmV3IGRpZ2l0cyBoYXZlIGJlZW4gZXJhc2VkIGZyb20gYW4gaWRlbnRpZmljYXRpb24gbnVtYmVyIGFuZCByZXBsYWNlZCB3aXRoIGEgY2hhcmFjdGVyICYjMzk7WCYjMzk7LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSB0aGUgdG90YWwgbnVtYmVyIG9mIGRpZmZlcmVudCBjb3JyZWN0IGlkZW50aWZpY2F0aW9uIG51bWJlcnMgY29ycmVzcG9uZGluZyB0byB0aGUgZ2l2ZW4gcGF0dGVybi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGdpdmVuIHBhdHRlcm4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIHRvdGFsIG51bWJlciBvZiBkaWZmZXJlbnQgY29ycmVjdCBpZGVudGlmaWNhdGlvbiBudW1iZXJzIGZyb20gdGhlIHByb2JsZW0gc3RhdGVtZW50LjxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgcmVzdWx0IHdpbGwgZml0IGludG8gdGhlIDY0LWJpdCBzaWduZWQgaW50ZWdlciB0eXBlIChpbnQ2NCBpbiBQYXNjYWwsIGxvbmcgbG9uZyBpbiBDXC9DKyspLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=