Background

Translated from ROIR 2021 Day 2 T4 A+B。

Problem Description

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$.

Input Format

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 Format

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

123
123
246

6

01
02
03

1

01211
12099
23300

4

121
214
999

0

Hint

[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$.

Translated by ChatGPT 5