Resident Registration Number

Suppose a new government uses the following 19-digit resident registration number format.

DDMMYYYYAAAAAAAAAAC

YYYY is the birth year, MM is the birth month, and DD is the birth day. The year is from 0001 through 9999, the month is from 01 through 12, and the day is from 01 through 31. Months 1, 3, 5, 7, 8, 10, and 12 have 31 days, while months 4, 6, 9, and 11 have 30 days. February has 28 days in a common year and 29 days in a leap year. A year YYYY is a leap year if it is divisible by 4 but not by 100, or if it is divisible by 400.

Each of the 10 positions marked A may be any digit. The last digit C is a control digit determined by the following algorithm.

1. Let the first 18 digits, excluding C, be Z1, Z2, ..., Z18 in order.
2. Compute S = (10*Z1 + 9*Z2 + 8*Z3 + ... + 2*Z9 + 10*Z10 + 9*Z11 + 8*Z12 + ... + 2*Z18) mod 19.
3. If S is at most 9, then C = S; otherwise, C = 19 - S.

Some digits of one number in this system have been erased. Count how many possible resident registration numbers match the given information and satisfy all the rules above.

The first line contains a 19-character string. Each character is either a digit or X. An X means that the digit in that position has been erased.

Print the number of possible resident registration numbers that satisfy the conditions. The answer is always less than 2^63.