Problem Description

There are three integers $a, b, c$ each of length $n$ possibly with leading zeros, arranged in three rows of $n$ columns as follows:

a
b
c

Determine the number of different column permutations such that the three integers $x, y, z$ read horizontally satisfy $x + y = z$ and none of the integers have leading zeros.

Since the number of permutations can be very large, output it modulo $10^9 + 7$.

Input Format

The first line contains an integer $a$ of length $n$.

The second line contains an integer $b$ of length $n$.

The third line contains an integer $c$ of length $n$.

Output Format

Output a single integer, the number of different permutation ways modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

123
123
246

Sample Output #1

6

Sample Input #2

01
02
03

Sample Output #2

1

Sample Input #3

01211
12099
23300

Sample Output #3

4

Sample Input #4

121
214
999

Sample Output #4

0

Notes

Sample Explanation 1: All permutations are valid.

Sample Explanation 2: We only count $10 + 20 = 30$, not $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 equation can be formed in two ways, resulting in a total of $2 \times 2 = 4$ valid permutations.

Data Range:

For all subtasks, $2 \le n \le 2 \times 10^5$.

见题面 Input 部分

见题面 Output 部分