Автор: | Михаил Путилин | Ограничение времени: | 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
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 7 | 2≤n≤6 | первая ошибка | |
2 | 14 | 2≤n≤18 | 1 | первая ошибка |
3 | 15 | 2≤n≤200, нет цифры ноль | первая ошибка | |
4 | 5 | 2≤n≤200 | 1–3 | первая ошибка |
5 | 17 | 2≤n≤750, нет цифры ноль | 3 | первая ошибка |
6 | 5 | 2≤n≤750 | 1–5 | первая ошибка |
7 | 20 | 2≤n≤2⋅105, нет цифры ноль | 3, 5 | первая ошибка |
8 | 17 | 2≤n≤2⋅105 | 1–7 | первая ошибка |
В первом примере подходят все перестановки столбцов.
Во втором примере единственная подходящая перестановка — 10+20=30. 01+02=03 не считается из-за наличия ведущих нулей.
В третьем примере возможны варианты 10121+21909=32030 и 12101+20919=33020, причём каждый из них может быть получен двумя разными перестановками.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|