24874번 - A+B 서브태스크다국어

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

01211
12099
23300

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

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

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

Во входных данных записаны целые неотрицательные числа $a$, $b$ и $c$ по одному в строке. Каждое число состоит из $n$ десятичных цифр и может начинаться с нуля ($2 \leq n \leq 2 \cdot 10^5$).

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

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

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

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