特工 Smart Beaver 在 ABBYY 的秘密研究部门工作。他在那里工作了很长时间,对自己的工作很满意,因为这让他可以在最好的餐厅吃饭,并在那里订购最昂贵和异国情调的木材类型。
内容特工接到了一项重要任务:获取英国科学家关于英语语言的最新研究成果。这些进展被编码并存储在一个大保险箱中。海狸的牙齿足够坚固,因此当局保证,海狸到达该地点后打开保险箱不会有任何问题。
他完成了他的白杨小枝并离开去执行这项重要任务。当然,海狸号毫无问题地到达了地点,但可惜了。他用他强壮而大的牙齿打不开保险箱。此时,聪明海狸接到总部的电话,得知不需要用牙齿打开保险箱,因为可靠的消息来源发送了以下信息:保险箱密码由数字组成,没有前导零。还有一个特殊的提示,可以用来打开保险箱。提示是具有以下结构的 string :
- 如果 si = "?",则安全代码中第 i 个数字可以是任何数字(0 到 9 之间(含));
- 如果 si 是数字(0 到 9 之间(含)),则表示代码中的第 i 位置有数字 si;
- 如果字符串包含从“A”到“J”的字母,则具有相同字母的所有位置必须包含相同的数字,并且具有不同字母的位置必须包含不同的数字。
- 安全代码的长度与提示的长度一致。
例如,提示“?JGJ9”有这样匹配的安全代码变体:“51919”、“55959”、“12329”、“93539”等,并且有错误变体如:“56669”、“00111”、“03539”和“13666”。
当局收到此类信息后改变计划,要求特工安静、轻柔地工作,不要尝试用机械方式打开保险箱,并尝试根据给出的提示找到密码。
在一所特工学校,聪明的海狸是他的排中查找此类保险箱密码最快的人,但现在他的情况不同了:岁月流逝……帮助他确定保险箱密码可能有多少种变体,与给定的提示相匹配。收到此信息并了解自己输入代码的速度后,智能海狸将能够确定他是否有时间观看今晚他最喜欢的电视频道上的节目“海狸在路上”,或者他应该彻夜不眠......
输入
第一行包含字符串 s — 安全代码的提示。字符串 s 由以下字符组成:?、0-9、A-J。保证字符串 s 的第一个字符不等于字符 0。
得分 30 分的输入限制为(子问题 A1):
- 1 ≤ |s| ≤ 5。
获得 100 分的输入限制为(子问题 A1+A2):
- 1 ≤ |s| ≤ 105。
这里 |s|表示字符串 s 的长度。
输出
打印与给定提示匹配的代码数。
示例
输入 #1
AJ
输出 #1
81
输入 #2
1?AA
输出 #2
100