Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача 8. A+B

Автор:Михаил Путилин   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Рассмотрим a, b и c — целые неотрицательные числа, записанные в десятичной системе счисления. Пусть они имеют одинаковую длину n, при этом запись может начинаться с нуля. Числа записаны одно под другим, цифры расположены в три строки и n столбцов. Рассмотрим пример такой записи:


  01211
  12099
  23300
  

Требуется переставить столбцы в этой записи таким образом, чтобы выполнялось равенство a+b=c. В полученной записи ведущие нули уже запрещены. Сколько существует различных способов это сделать?

Перестановки столбцов считаются различными, даже если полученные записи совпадают. Например, если в записи выше переставить два последних столбца, получится другая перестановка, хотя цифры в этих колонках совпадают.

Поскольку ответ может быть довольно большим, требуется посчитать для него остаток по модулю 109+7.

Формат входных данных

Во входных данных записаны целые неотрицательные числа a, b и c по одному в строке. Каждое число состоит из n десятичных цифр и может начинаться с нуля.

Формат выходных данных

Выведите количество подходящих перестановок столбцов по модулю 109+7.

Ограничения

2n2105

Система оценки

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
172n6первая ошибка
2142n181первая ошибка
3152n200, нет цифры нольпервая ошибка
452n2001–3первая ошибка
5172n750, нет цифры ноль3первая ошибка
652n7501–5первая ошибка
7202n2105, нет цифры ноль3, 5первая ошибка
8172n21051–7первая ошибка

Пояснения к примерам

В первом примере подходят все перестановки столбцов.

Во втором примере единственная подходящая перестановка — 10+20=30. 01+02=03 не считается из-за наличия ведущих нулей.

В третьем примере возможны варианты 10121+21909=32030 и 12101+20919=33020, причём каждый из них может быть получен двумя разными перестановками.

Примеры тестов

Стандартный вход Стандартный выход
1
123
123
246
6
2
01
02
03
1
3
01211
12099
23300
4
4
121
214
999
0

0.074s 0.008s 13