시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 23 10 10 43.478%

문제

내일이면 대한민국에 새로운 대통령이 취임하게 된다. 새로운 정부는, 아래와 같이 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보다 작다.

예제 입력

XX0220051234567890X

예제 출력

28

힌트