E. B + C
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Очень часто на пробном туре соревнований участникам предлагается задача $$$A + B$$$. Организаторы соревнований, в которых участвует Кеша, так и поступили. А на основном туре предложили другую задачу, $$$B + C$$$.

Кеше нравятся короткие условия, поэтому он сразу же взялся решать эту задачу.

На доске записали равенство $$$A = B + C$$$, где $$$A$$$, $$$B$$$ и $$$C$$$ — целые положительные числа без ведущих нулей.

Затем некоторые цифры в равенстве стёрли.

Ваша задача (и Кеши, конечно, тоже) — определить, сколькими способами можно восстановить стёртые цифры, чтобы равенство осталось верным.

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

В первой строке записано число $$$A$$$ $$$(1 \le |A| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.

Во второй строке записано число $$$B$$$ $$$(1 \le |B| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.

В третьей строке записано число $$$C$$$ $$$(1 \le |C| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.

Символы # заменяют стёртые цифры.

Гарантируется, что $$$A$$$, $$$B$$$, $$$C$$$:

  • содержат только символы 0-9 и #;
  • не начинаются с (ведущего) нуля.
Выходные данные

Обозначим через $$$m$$$ количество способов заменить знаки # на десятичные цифры 0-9 согласно условию задачи. Поскольку число $$$m$$$ может быть очень большим, выведите остаток от деления $$$m$$$ на $$$10^9 + 7$$$.

Способ считается верным, если при замене цифр:

  • выполняется равенство $$$A = B + C$$$;
  • числа $$$A$$$, $$$B$$$, $$$C$$$ —положительные;
  • числа $$$A$$$, $$$B$$$, $$$C$$$ не начинаются с ведущего нуля.
Система оценки

Во всех подзадачах баллы начисляются только в случае прохождения всех тестов этой подзадачи и необходимых подзадач.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
10 (10)$$$|A|, |B|, |C| \le 3$$$нетпервая ошибка
20 (10)$$$|A|, |B|, |C| \le 5$$$, $$$A$$$ не содержит #нетпервая ошибка
30 (10)$$$|A|, |B| \le 5$$$, $$$|C| \le 2$$$нетпервая ошибка
40 (10)$$$|A|, |B|, |C| \le 5$$$1, 2, 3первая ошибка
50 (15)$$$A$$$ не содержит #, $$$|C| \le 2$$$нетпервая ошибка
60 (15)$$$A$$$ не содержит #2, 5первая ошибка
70 (15)$$$|C| \le 2$$$3, 5первая ошибка
80 (15)любые допустимые значения4, 6, 7первая ошибка

Примеры
Входные данные
12#
#4
57
Выходные данные
1
Входные данные
968
#0#
8#
Выходные данные
0
Входные данные
9
#
#
Выходные данные
8
Примечание

Поясним приведённые примеры.

Первый пример Единственный возможный способ восстановить значения:

  • $$$A = 121$$$;
  • $$$B = 64$$$;
  • $$$C = 57$$$.

Второй пример

Невозможно восстановить ни одним способом.

Как легко заметить, в числе $$$B$$$ десятков $$$0$$$, в $$$C$$$ десятков $$$8$$$, а в числе $$$A$$$ десятков $$$6$$$.

Третий пример

Подойдут следующие способы:

  • $$$1 + 8$$$;
  • $$$2 + 7$$$;
  • ...
  • $$$8 + 1$$$.