Задачи
Подсчет забавных чисел
Подсчет забавных чисел
Вы думаете считать легко? Это не тот случай, когда Вы полностью понимаете природу объектов, которые следует посчитать.
Назовем \textbf{2N}-значное целое число \textbf{X} (возможно с ведущими нулями) забавным, если существует два таких \textbf{N}-значных целых числа \textbf{a} и \textbf{b} (возможно с ведущими нулями), что \textbf{a} + \textbf{b} = \textbf{10^N} и \textbf{S_d}(\textbf{X}) = \textbf{S_d}(\textbf{a}) + \textbf{S_d}(\textbf{b}) имеет место для каждой цифры \textbf{d}, где \textbf{S_d}(\textbf{P}) (\textbf{0 }≤ \textbf{d }≤ \textbf{9}) - количество вхождений цифры \textbf{d} в десятичной записи \textbf{P}. Например, числа \textbf{46} (\textbf{4} + \textbf{6} = \textbf{10^1}), \textbf{9820} (\textbf{98} + \textbf{02} = \textbf{10^2}) и \textbf{08362090} (\textbf{6020} + \textbf{3980} = \textbf{10^4}) являются забавными.
Задана последовательность цифр и знаков вопроса четной длины. Найдите количество способов, которыми можно заменить знаки вопроса цифрами, чтобы получить забавное число. Ответ следует найти по модулю \textbf{10^9} + \textbf{7}.
\InputFile
Единственная строка содержит непустую последовательность цифр и знаков вопроса. Длина последовательности четная и не превосходит \textbf{10^5}. Количество знаков вопроса не превосходит \textbf{1000}.
\OutputFile
Вывести искомое количество способов по модулю \textbf{10^9} + \textbf{7}.
Входные данные #1
2?4?
Выходные данные #1
4