Задача 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.

Ограничения

2 ≤ n ≤ 2 ⋅ 105

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

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
172 ≤ n ≤ 6первая ошибка
2142 ≤ n ≤ 181первая ошибка
3152 ≤ n ≤ 200, нет цифры нольпервая ошибка
452 ≤ n ≤ 2001–3первая ошибка
5172 ≤ n ≤ 750, нет цифры ноль3первая ошибка
652 ≤ n ≤ 7501–5первая ошибка
7202 ≤ n ≤ 2 ⋅ 105, нет цифры ноль3, 5первая ошибка
8172 ≤ n ≤ 2 ⋅ 1051–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.112s 0.012s 13