A2. Спецзадание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Специальный агент Умный Бобер работает в отделе секретных исследований и разработок компании ABBYY. Трудится он там уже достаточно давно и доволен своей работой, так как она позволяет ему питаться в лучших лесных ресторанах и заказывать в них самые дорогие и экзотические породы древесины.

Довольный жизнью наш спецагент получает очередное важное задание: необходимо заполучить новейшие разработки британских ученых в области английского языка. Эти разработки засекречены и хранятся в большом сейфе. Зубы у бобра достаточно крепки, потому начальство уверено, что по прибытии на место вскрытие сейфа не вызовет сложностей.

И вот он уже доедает свою веточку осины и выходит на это важное задание. Естественно, прибыть на место у Умного Бобра труда не составило, а вот вскрыть сейф своими крепкими и большими зубами, увы, не получается. В этот момент с Умным Бобром связывается штаб и сообщает, что вскрывать зубами сейф нет необходимости, так как из достоверного источника была получена следующая информация: код от сейфа состоит из цифр и не имеет лидирующих нулей. Также была получена специальная подсказка, с помощью которой можно открыть сейф. Подсказка представляет собой строку s со следующей структурой:

  • если si = «?», то цифра, стоящая в коде от сейфа на позиции i может быть любой (от 0 до 9);
  • если si цифра от 0 до 9, то значит, в коде на позиции i строит цифра si;
  • если в строке s встречаются буквы от «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.

Выходные данные

Выведите количество кодов, которые подходят к заданной подсказке.

Примеры
Входные данные
AJ
Выходные данные
81
Входные данные
1?AA
Выходные данные
100