题目描述
AHHF研究所是世界顶级研究所之一。为了防止最新成果泄露,研究所所长决定给每个人发放一张个人身份证,每个身份证都是由19位数字组成的,形式是:
DDMMYYYYAAAAAAAAAAC
前8位数字表示了持有人的生日,DD为日,MM为月,YYYY为年。在这里,我们认为出生年份是一个0001到9999之间的正整数。
字母A表示的位置可以是任意的数字(0-9),C是由如下算法得到的控制数字:
1、用Z1…Z18表示身份证中前18位数字
2、S =
(10*Z1+9*Z2+8*Z3+…+2*Z9+10*Z10+9*Z11+8*Z12+…+2*Z18) mod 19
3、如果S≤9那么C = S,否则C = 19-S
前几天,保安们从一名来历不明的入侵者身上搜到了一张身份证,不料身份证上已有多处已经残缺之处,看不清了,我们用X表示。现在的问题是,计算有多少种可能的身份证与得到的身份证相符合?这对下一步调查工作非常重要!所长将这份工作交给了小雪,你能帮助小雪解决这个难题嘛?
输入格式
仅包含一行,按照上面给出的格式描述了得到的身份证。
输出格式
包含一个数字,表示所有可能的满足条件的身份证的个数。我们保证这个数目不会超过64位有符号整数能够表示的范围
样例输入
样例输出