CF316A2.Special Task

Special Agent Smart Beaver works in a secret research department of ABBYY. He's been working there for a long time and is satisfied with his job, as it allows him to eat out in the best restaurants and order the most expensive and exotic wood types there.

The content special agent has got an important task: to get the latest research by British scientists on the English Language. These developments are encoded and stored in a large safe. The Beaver's teeth are strong enough, so the authorities assured that upon arriving at the place the beaver won't have any problems with opening the safe.

And he finishes his aspen sprig and leaves for this important task. Of course, the Beaver arrived at the location without any problems, but alas. He can't open the safe with his strong and big teeth. At this point, the Smart Beaver get a call from the headquarters and learns that opening the safe with the teeth is not necessary, as a reliable source has sent the following information: the safe code consists of digits and has no leading zeroes. There also is a special hint, which can be used to open the safe. The hint is string s with the following structure:

• if s__i = "?", then the digit that goes i-th in the safe code can be anything (between 0 to 9, inclusively);
• if s__i is a digit (between 0 to 9, inclusively), then it means that there is digit s__i on position i in code;
• if the string contains letters from "A" to "J", then all positions with the same letters must contain the same digits and the positions with distinct letters must contain distinct digits.
• The length of the safe code coincides with the length of the hint.

For example, hint "?JGJ9" has such matching safe code variants: "51919", "55959", "12329", "93539" and so on, and has wrong variants such as: "56669", "00111", "03539" and "13666".

After receiving such information, the authorities change the plan and ask the special agents to work quietly and gently and not to try to open the safe by mechanical means, and try to find the password using the given hint.

At a special agent school the Smart Beaver was the fastest in his platoon finding codes for such safes, but now he is not in that shape: the years take their toll ... Help him to determine the number of possible variants of the code to the safe, matching the given hint. After receiving this information, and knowing his own speed of entering codes, the Smart Beaver will be able to determine whether he will have time for tonight's show "Beavers are on the trail" on his favorite TV channel, or he should work for a sleepless night...

特工聪明的海狸在ABBYY公司的一家秘密研究部门工作。他在这里工作已久，对这份工作非常满意，因为这使他能光顾最好的餐厅，并在那里点最昂贵、最稀有的木材（注：此处为幽默双关，原文“wood types”实为“words”的谐音梗，但按字面直译为“木材种类”，保留原文修辞风格）。

这位特工接到一项重要任务：获取英国科学家关于英语语言的最新研究成果。这些研究成果经过编码后，被存放在一个大型保险箱中。海狸的牙齿非常坚固，因此上级曾向他保证：抵达现场后，他仅凭自己强健有力的大牙便能轻松打开保险箱。

于是，海狸嚼完最后一根白杨嫩枝，便出发执行这项重要任务。当然，他顺利抵达了目的地，但遗憾的是——他竟无法用自己那强壮又巨大的牙齿打开保险箱！就在此时，总部打来电话，告知他其实无需动用牙齿开锁；一位可靠情报源已发来如下信息：保险箱密码由数字组成，且不含前导零。此外，还附有一条特殊提示，可用于开启保险箱。该提示是一串字符串 $ s $，其结构如下：

• 若 $ s_i = \text{?} $，则密码中第 $ i $ 位可以是任意数字（即 $ 0 $ 至 $ 9 $ 中的任一数字，含端点）；
• 若 $ s_i $ 是一个数字（即 $ 0 $ 至 $ 9 $ 中的某一位数字，含端点），则表示密码中第 $ i $ 位必须恰好是该数字；
• 若字符串中包含字母 'A' 至 'J'，则所有相同字母所对应的位置上必须填入相同的数字，而不同字母所对应的位置上必须填入互不相同的数字；
• 密码长度与提示字符串 $ s $ 的长度完全一致。

例如，提示字符串 "?JGJ9" 对应的合法密码有："51919"、"55959"、"12329"、"93539" 等；而不合法的密码包括："56669"（J 和 G 位置数字相同，违反“不同字母须对应不同数字”）、"00111"（首位为 0，违反“无前导零”）、"03539"（首位为 0）、"13666"（J 和 G 位置数字相同）等。

收到该信息后，上级立即调整计划，要求特工们务必安静、谨慎地工作，不得尝试以机械方式强行开锁，而应利用所给提示推导出密码。

在特工学校受训期间，聪明的海狸曾是全排破解此类保险箱密码速度最快者；但如今，岁月不饶人……请帮助他计算：满足给定提示的所有可能密码数量是多少？ 得知这一数目后，再结合他自己输入密码的速度，聪明的海狸便能判断：今晚是否还能赶上看他最爱的电视节目《追踪中的河狸》（Beavers are on the trail），抑或不得不彻夜奋战……

The first line contains string s — the hint to the safe code. String s consists of the following characters: ?, 0-9, A-J. It is guaranteed that the first character of string s doesn't equal to character 0.

The input limits for scoring 30 points are (subproblem A1):

• 1 ≤ |s| ≤ 5.

The input limits for scoring 100 points are (subproblems A1+A2):

• 1 ≤ |s| ≤ 105.

Here |s| means the length of string s.

第一行包含字符串 $s$ —— 保险箱密码的提示。字符串 $s$ 仅由以下字符组成：?、0-9、A-J。保证字符串 $s$ 的第一个字符不为字符 0。

得分为 30 分的输入限制（子问题 A1）：

• $1 ≤ |s| ≤ 5$。

得分为 100 分的输入限制（子问题 A1 + A2）：

• $1 ≤ |s| ≤ 10^5$。

其中 $|s|$ 表示字符串 $s$ 的长度。

Print the number of codes that match the given hint.

输出符合给定提示的密码数量。