Задачі
Підрахунок кумедних чисел
Підрахунок кумедних чисел
Ви думаєте рахувати легко? Це не той випадок, коли Ви повністю розумієте природу об'єктів, які потрібно порахувати.
Назвемо \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