P9768 [ROIR 2021] A+B (Day 2)

**Translated from [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day 2 T4 [A+B](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。

There are three integers $a, b, c$ of length $n$, which may contain leading zeros. They are arranged into three rows and $n$ columns as follows: ``` a b c ``` How many different ways are there to permute the **columns** so that the three integers read horizontally, $x, y, z$, satisfy $x + y = z$, and none of the three integers has leading zeros. The number of permutations may be large; output it $\bmod \ 10^9+7$.

The first line is an integer $a$ of length $n$. The second line is an integer $b$ of length $n$. The third line is an integer $c$ of length $n$.

Output one integer: the number of different permutations modulo $10^9+7$.

[Sample Explanation 1]: All permutations are valid. [Sample Explanation 2]: We only count $10 + 20 = 30$, and we do not count $01 + 02 = 03$, because $03$ has a leading zero. [Sample Explanation 3]: Clearly, there are two valid equations: $10121 + 21909 = 32030$ and $12101 + 20919 = 33020$. However, since there are two identical columns, each of them has two ways to obtain the answer. The total number of valid permutations is $2 \times 2 = 4$. [Constraints]: For all subtasks, $2 \le n \le 2 \times 10^5$. | Subtask ID | Special Constraints | Score | | :-: | :-: | :-: | | $1$ | $n \le 6$ | $7$ | | $2$ | $n \le 18$ | $14$ | | $3$ | $n \le 200$, the input numbers do not contain $0$ | $15$ | | $4$ | $n \le 200$ | $5$ | | $5$ | $n \le 750$, the input numbers do not contain $0$ | $17$ | | $6$ | $n \le 750$ | $5$ | | $7$ | the input numbers do not contain $0$ | $20$ | | $8$ | no special constraints | $17$ | Translated by ChatGPT 5