题目描述

特工 Smart Beaver 在 ABBYY 的一个秘密研究部门工作。他在那里工作了很久，对自己的工作很满意，因为这份工作让他能在最好的餐厅用餐，并点最昂贵、最奇特的木材。

这位满足的特工接到了一个重要任务：获取英国科学家关于英语语言的最新研究成果。这些成果已经被加密并存储在一个大型保险箱中。海狸的牙齿足够坚固，所以上级保证他到达现场后，打开保险箱不会有任何问题。

他吃完了他的白杨树枝，便踏上了这项重要任务。当然，海狸顺利到达了现场，但不幸的是，他无法用自己强壮的大牙打开保险箱。就在这时，Smart Beaver 接到了总部的电话，得知其实并不需要用牙齿开箱，因为可靠消息源已经发送了如下信息：保险箱的密码由数字组成，且没有前导零。同时还有一个特殊的提示字符串 $s$，可以用来打开保险箱。提示字符串 $s$ 的结构如下：

• 如果 $s_i$ 是“?”，那么密码的第 $i$ 位可以是任意数字（$0$ 到 $9$，包括 $0$ 和 $9$）；
• 如果 $s_i$ 是数字（$0$ 到 $9$），那么密码的第 $i$ 位必须是该数字；
• 如果字符串中包含“A”到“J”的字母，则所有相同字母的位置必须填相同的数字，不同字母的位置必须填不同的数字。
• 密码的长度与提示字符串的长度相同。

例如，提示字符串“?JGJ9”有如下合法的密码方案：“51919”、“55959”、“12329”、“93539”等等；而以下方案不合法：“56669”、“00111”、“03539”、“13666”。

收到这些信息后，上级改变了计划，要求特工们安静温和地工作，不要用机械手段开箱，而是尝试用提示找到密码。

在特工学校时，Smart Beaver 是全班最快找出这种保险箱密码的人，但现在他已不复当年勇……请你帮他计算，符合给定提示的密码方案有多少种。得到这个信息后，Smart Beaver 就能根据自己输入密码的速度，判断今晚能否赶上他最喜欢的电视节目《海狸追踪》，还是得熬夜工作……

输入格式

第一行包含字符串 $s$，即保险箱密码的提示。字符串 $s$ 只包含以下字符：?、0-9、A-J。保证字符串 $s$ 的第一个字符不是 $0$。

对于 30 分的测试点（子任务 A1）：

• $1 \leq |s| \leq 5$。

对于 100 分的测试点（子任务 A1+A2）：

• $1 \leq |s| \leq 10^5$。

这里 $|s|$ 表示字符串 $s$ 的长度。

输出格式

输出符合给定提示的密码方案总数。

说明/提示

由 ChatGPT 4.1 翻译

样例

AJ

81

1?AA

100