시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 24 11 11 45.833%

문제

내일이면 대한민국에 새로운 대통령이 취임하게 된다. 새로운 정부는, 아래와 같이 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는 숫자가 지워졌음을 의미한다.

출력

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

예제 입력 1

XX0220051234567890X

예제 출력 1

28

힌트

W3sicHJvYmxlbV9pZCI6IjE2NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjBiNFx1Yzc3Y1x1Yzc3NFx1YmE3NCBcdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmRcdWM1ZDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YjMwMFx1ZDFiNVx1YjgzOVx1Yzc3NCBcdWNkZThcdWM3ODRcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjODE1XHViZDgwXHViMjk0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDE5XHVjNzkwXHViOWFjXHViODVjIFx1YjQxYyBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjOGZjXHViYmZjXHViNGYxXHViODVkXHViYzg4XHVkNjM4IFx1Y2NiNFx1YWNjNFx1Yjk3YyBcdWIzYzRcdWM3ODVcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5ERE1NWVlZWUFBQUFBQUFBQUFDPFwvcD5cclxuXHJcbjxwPllZWVlcdWIyOTQgXHVjMGRkXHViMTQ0LCBNTVx1Yzc0MCBcdWMwZGRcdWM2ZDQsIEREXHViMjk0IFx1YzBkZFx1Yzc3Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzBkZFx1YjE0NFx1Yzc0MCAwMDAxIFx1Yzc3NFx1YzBjMSA5OTk5IFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWMyMThcdWFjMDAgXHViNDE4XHViYTcwLCBNTVx1Yzc0MCAwMSBcdWM3NzRcdWMwYzEgMTIgXHVjNzc0XHVkNTU4LCBERFx1YjI5NCAwMSBcdWM3NzRcdWMwYzEgMzEgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiAxLCAzLCA1LCA3LCA4LCAxMCwgMTJcdWM2ZDRcdWM3NDAgMzFcdWM3N2NcdWFlNGNcdWM5YzAsIDQsIDYsIDksIDExXHVjNmQ0XHVjNzQwIDMwXHVjNzdjXHVhZTRjXHVjOWMwXHVjNzc0XHViYTcwLCAyXHVjNmQ0XHVjNzQwIFx1ZDNjOVx1YjE0NFx1Yzc0MCAyOFx1Yzc3Y1x1YWU0Y1x1YzljMCwgXHVjNzI0XHViMTQ0XHVjNzQwIDI5XHVjNzdjXHVhZTRjXHVjOWMwXHVjNzc0XHViMmU0LiBcdWM3MjRcdWIxNDRcdWM3NzRcdWI3ODAgWVlZWVx1YWMwMCAoMSkgMTAwXHVjNzU4IFx1YmMzMFx1YzIxOFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgNFx1Yzc1OCBcdWJjMzBcdWMyMThcdWM3NzRcdWFjNzBcdWIwOTggKDIpIDQwMFx1Yzc1OCBcdWJjMzBcdWMyMThcdWM3NzggXHVhY2JkXHVjNmIwXHVhYzAwIFx1ZDU3NFx1YjJmOVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+QVx1Yjg1YyBcdWI0MWMgMTBcdWM3OTBcdWI5YWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzIyYlx1Yzc5MFx1Yjc3Y1x1YjNjNCBcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1Yzc5MFx1YjlhY1x1Yzc3OCBDXHViMjk0IENPTlRST0wtRElHSVRcdWM3M2NcdWI4NWMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWMwZGRcdWMxMzFcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Q1x1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHVjOGZjXHViYmZjXHViNGYxXHViODVkXHViYzg4XHVkNjM4XHVjMGMxXHVjNzU4IDE4XHVjNzkwXHViOWFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgWjEsIFoyLCAmaGVsbGlwOywgWjE4XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9saT5cclxuXHQ8bGk+UyA9ICgxMCZ0aW1lcztaMSArIDkmdGltZXM7WjIgKyA4JnRpbWVzO1ozICsgJmhlbGxpcDsgKyAyJnRpbWVzO1o5ICsgMTAmdGltZXM7WjEwICsgOSZ0aW1lcztaMTEgKyA4JnRpbWVzO1oxMiArICZoZWxsaXA7ICsgMiZ0aW1lcztaMTgpICUgMTk8XC9saT5cclxuXHQ8bGk+U1x1YWMwMCA5IFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YmE3NCBDPVMsIFx1YzU0NFx1YjJjOFx1YmE3NCBDID0gMTkgLSBTPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzggXHVjY2I0XHVhY2M0XHVjMGMxXHVjNzU4IFx1ZDU1YyBcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzhcdWM3NTggXHVjNzdjXHViZDgwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzhmY1x1YmJmY1x1YjRmMVx1Yjg1ZFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YzEzOFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAxOVx1Yzc5MFx1YjlhY1x1Yzc1OCBcdWM4ZmNcdWJiZmNcdWI0ZjFcdWI4NWRcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMmJcdWM3OTAgXHViNjEwXHViMjk0IFhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxOFx1YjI5NFx1YjM3MCBYXHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM4NGNcdWM3NGNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzhmY1x1YmJmY1x1YjRmMVx1Yjg1ZFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSAyXjYzXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjY0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiam1iZyIsImRlc2NyaXB0aW9uIjoiPHA+RXZlcnkgY2l0aXplbiBpbiBvbmUgY291bnRyeSBoYXMgaGlzIG93biBpZGVudGlmaWNhdGlvbiBudW1iZXIgY29uc2lzdGluZyBvZiAxOSBkaWdpdHMgaW4gdGhlIGZvcm1hdDombmJzcDs8XC9wPlxyXG5cclxuPHA+RERNTVlZWVlBQUFBQUFBQUFBQyZuYnNwOzxcL3A+XHJcblxyXG48cD53aGVyZSBkaWdpdHMgREQgZGVub3RlIGRheSwgTU0gbW9udGgsIGFuZCBZWVlZIHllYXIgb2YgdGhlIGJpcnRoLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ZZWFyIG9mIGJpcnRoIGlzIGEgcG9zaXRpdmUgaW50ZWdlciBiZXR3ZWVuIDAwMDEgYW5kIDk5OTkgaW5jbHVzaXZlLiBZZWFyIGlzIGEgbGVhcCB5ZWFyIGlmIGl0IGlzIGRpdmlzaWJsZSBieSA0LCBidXQgbm90IGJ5IDEwMCBvciBpZiBpdCBpcyBkaXZpc2libGUgYnkgNDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EaWdpdHMgZGVub3RlZCBieSBBIGNhbiBiZSBhcmJpdHJhcnksIGFuZCBDIGlzIGEgY29udHJvbC1kaWdpdCBjYWxjdWxhdGVkIGJ5IHRoZSBmb2xsb3dpbmcgYWxnb3JpdGhtOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkRlbm90ZSBhbGwgdGhlIGRpZ2l0cyBpbiBpZGVudGlmaWNhdGlvbiBudW1iZXIsIGV4Y2VwdCB0aGUgbGFzdCBvbmUsIHdpdGggWjEuLi5aMTgmbmJzcDs8XC9saT5cclxuXHQ8bGk+UyA9ICgxMCpaMSs5KloyKzgqWjMrIC4uLiArMipaOSsxMCpaMTArOSpaMTErOCpaMTIrIC4uLiArMipaMTgpIG1vZCAxOSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5pZiBTICZsZTsgOSB0aGVuIEMgPSBTLCBvdGhlcndpc2UgQyA9IDE5LVMmbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5BIGZldyBkaWdpdHMgaGF2ZSBiZWVuIGVyYXNlZCBmcm9tIGFuIGlkZW50aWZpY2F0aW9uIG51bWJlciBhbmQgcmVwbGFjZWQgd2l0aCBhIGNoYXJhY3RlciAmIzM5O1gmIzM5Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIHRvdGFsIG51bWJlciBvZiBkaWZmZXJlbnQgY29ycmVjdCBpZGVudGlmaWNhdGlvbiBudW1iZXJzIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGdpdmVuIHBhdHRlcm4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBnaXZlbiBwYXR0ZXJuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSB0b3RhbCBudW1iZXIgb2YgZGlmZmVyZW50IGNvcnJlY3QgaWRlbnRpZmljYXRpb24gbnVtYmVycyBmcm9tIHRoZSBwcm9ibGVtIHN0YXRlbWVudC48XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIHJlc3VsdCB3aWxsIGZpdCBpbnRvIHRoZSA2NC1iaXQgc2lnbmVkIGludGVnZXIgdHlwZSAoaW50NjQgaW4gUGFzY2FsLCBsb25nIGxvbmcgaW4gQ1wvQysrKS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=