Jmbg

Every citizen in one country has his own identification number consisting of 19 digits in the format: DDMMYYYYAAAAAAAAAAC where digits DD denote day, MM month, and YYYY year of the birth. Year of birth is a positive integer between 0001 and 9999 inclusive. Year is a leap year if it is divisible by 4, but not by 100 or if it is divisible by 400. Digits denoted by A can be arbitrary, and [] is a control-digit calculated by the following algorithm:
1. Denote all the digits in identification number, except the last one, with Z1...Z18
2. S = (10*Z1+9*Z2+8*Z3+ ... +2*Z9+10*Z10+9*Z11+8*Z12+ ... +2*Z18) mod 19
3. if S ≤ 9 then C = S, otherwise C = 19-S A few digits have been erased from an identification number and replaced with a character 'X'.
Write a program that will calculate the total number of different correct identification numbers corresponding to the given pattern.