주민등록번호
시간 제한2초메모리 제한128 MB
일부 숫자가 X로 지워진 19자리 주민등록번호 패턴에서 올바른 생년월일과 체크섬 규칙을 모두 만족하는 완성 가능한 번호의 개수를 구합니다.
문제
새 정부가 다음과 같은 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가 100의 배수가 아닌 4의 배수이거나 400의 배수이면 윤년이다.
A로 표시된 10자리는 각각 어떤 숫자라도 될 수 있다. 마지막 자리 C는 제어 숫자이며, 다음 알고리즘으로 정해진다.
C를 제외한 앞 18자리 숫자를 순서대로Z1, Z2, ..., Z18이라고 한다.S = (10*Z1 + 9*Z2 + 8*Z3 + ... + 2*Z9 + 10*Z10 + 9*Z11 + 8*Z12 + ... + 2*Z18) mod 19를 계산한다.S가 9 이하이면C = S이고, 그렇지 않으면C = 19 - S이다.
이 체계의 주민등록번호 일부 숫자가 지워져 있다. 주어진 정보와 위 조건을 모두 만족하는 가능한 주민등록번호의 개수를 구하시오.
입력
첫째 줄에 19자리 문자열이 주어진다. 각 문자는 숫자이거나 X이다. X는 해당 숫자가 지워졌음을 뜻한다.
출력
조건을 만족하는 가능한 주민등록번호의 개수를 첫째 줄에 출력한다. 답은 항상 2^63보다 작다.