Задача №114542. A+B
Рассмотрим \(a\), \(b\) и \(c\) — целые неотрицательные числа, записанные в десятичной системе счисления. Пусть они имеют одинаковую длину \(n\), при этом запись может начинаться с нуля. Числа записаны одно под другим, цифры расположены в три строки и \(n\) столбцов. Рассмотрим пример такой записи:
Требуется переставить столбцы в этой записи таким образом, чтобы выполнялось равенство \(a+b=c\). В полученной записи ведущие нули уже запрещены. Сколько существует различных способов это сделать?
Перестановки столбцов считаются различными, даже если полученные записи совпадают. Например, если в записи выше переставить два последних столбца, получится другая перестановка, хотя цифры в этих колонках совпадают.
Поскольку ответ может быть довольно большим, требуется посчитать для него остаток по модулю \(10^9+7\).
Во входных данных записаны целые неотрицательные числа \(a\), \(b\) и \(c\) по одному в строке. Каждое число состоит из \(n\) десятичных цифр и может начинаться с нуля (\(2 \leq n \leq 2 \cdot 10^5\)).
Выведите количество подходящих перестановок столбцов по модулю \(10^9+7\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 7 | \(2 \leq n \leq 6\) | первая ошибка | |
| 2 | 14 | \(2 \leq n \leq 18\) | 1 | первая ошибка |
| 3 | 15 | \(2 \leq n \leq 200\), нет цифры ноль | первая ошибка | |
| 4 | 5 | \(2 \leq n \leq 200\) | 1–3 | первая ошибка |
| 5 | 17 | \(2 \leq n \leq 750\), нет цифры ноль | 3 | первая ошибка |
| 6 | 5 | \(2 \leq n \leq 750\) | 1–5 | первая ошибка |
| 7 | 20 | \(2 \leq n \leq 2 \cdot 10^5\), нет цифры ноль | 3, 5 | первая ошибка |
| 8 | 17 | \(2 \leq n \leq 2 \cdot 10^5\) | 1–7 | первая ошибка |
В первом примере подходят все перестановки столбцов.
Во втором примере единственная подходящая перестановка — \(10+20=30\). \(01+02=03\) не считается из-за наличия ведущих нулей.
В третьем примере возможны варианты \(10121+21909=32030\) и \(12101+20919=33020\), причём каждый из них может быть получен двумя разными перестановками.
123 123 246
6
01 02 03
1
01211 12099 23300
4
121 214 999
0