Подсчет забавных чисел
Вы думаете считать легко? Это не тот случай, когда Вы полностью понимаете природу объектов, которые следует посчитать.
Назовем 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.