Очень часто на пробном туре соревнований участникам предлагается задача $$$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$$$:
Обозначим через $$$m$$$ количество способов заменить знаки # на десятичные цифры 0-9 согласно условию задачи. Поскольку число $$$m$$$ может быть очень большим, выведите остаток от деления $$$m$$$ на $$$10^9 + 7$$$.
Способ считается верным, если при замене цифр:
Во всех подзадачах баллы начисляются только в случае прохождения всех тестов этой подзадачи и необходимых подзадач.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 0 (10) | $$$|A|, |B|, |C| \le 3$$$ | нет | первая ошибка |
| 2 | 0 (10) | $$$|A|, |B|, |C| \le 5$$$, $$$A$$$ не содержит # | нет | первая ошибка |
| 3 | 0 (10) | $$$|A|, |B| \le 5$$$, $$$|C| \le 2$$$ | нет | первая ошибка |
| 4 | 0 (10) | $$$|A|, |B|, |C| \le 5$$$ | 1, 2, 3 | первая ошибка |
| 5 | 0 (15) | $$$A$$$ не содержит #, $$$|C| \le 2$$$ | нет | первая ошибка |
| 6 | 0 (15) | $$$A$$$ не содержит # | 2, 5 | первая ошибка |
| 7 | 0 (15) | $$$|C| \le 2$$$ | 3, 5 | первая ошибка |
| 8 | 0 (15) | любые допустимые значения | 4, 6, 7 | первая ошибка |
12##457
1
968#0#8#
0
9##
8
Поясним приведённые примеры.
Первый пример Единственный возможный способ восстановить значения:
Второй пример
Невозможно восстановить ни одним способом.
Как легко заметить, в числе $$$B$$$ десятков $$$0$$$, в $$$C$$$ десятков $$$8$$$, а в числе $$$A$$$ десятков $$$6$$$.
Третий пример
Подойдут следующие способы: