Підрахунок кумедних чисел
Ви думаєте рахувати легко? Це не той випадок, коли Ви повністю розумієте природу об'єктів, які потрібно порахувати.
Назвемо 2N-значне ціле число X (можливо з ведучими нулями) кумедним, якщо існує два таких N-значних цілих числа a та b (можливо з ведучими нулями), що a + b = 10^N та S_d(X) = S_d(a) + S_d(b) має місце для кожної цифри d, де S_d(P) (0 ≤ d ≤ 9) - кількість входжень цифри d у десятковий запис P. Наприклад, числа 46 (4 + 6 =10^1), 9820 (98 + 02 = 10^2) та 08362090 (6020 + 3980 = 10^4) є кумедними.
Задано послідовність цифр та знаків питання парної довжини. Знайдіть кількість способів, якими можна замінити знаки питання цифрами, щоб отримати кумедне число. Відповідь потрібно знайти по модулю 10^9 + 7.
Вхідні дані
Єдиний рядок містить непорожню послідовність цифр та знаків питання. Довжина послідовності парна і не перевищує 10^5. Кількість знаків питання не перевищує 1000.
Вихідні дані
Вивести шукану кількість способів по модулю 10^9 + 7.