Description

Translated from ROIR 2021 Day2 T4 A+B on this website.

There are three integers $a,~b,~c$ with length $n$ which may consist of prefix zeros with the following layout that has three lines and $n$ columns.

a
b
c

Your task is to find the number of ways arranging the columns in which the three integers $x,~y,~z$ horizontally read satisfies that $x+y=z$ and that all those numbers have no prefix zeros.

Since it is possible that large amount of solutions exist, it is only required to output the number of solutions $\bmod 10^9+7$.

Input Format

Three lines with each line consists of an integer of length $n$.

Output Format

The number of solutions $\bmod 10^9+7$.

123
123
246

6

All ways of arranging the columns satisfy the conditions.

01
02
03

1

Only $10+20=30$ satisfies the condition since $01+02=03$ consists of prefix zeros.

01211
12099
23300

4

It is obvious that both $10121 + 21909 = 32030$ and $12101 + 20919 = 33020$ satisfy the condition but, for each of these solutions, there are two ways of obtaining them. Thus the total number of ways are $2\times 2=4$.

121
214
999

0

Constraints

For all test data, it is guaranteed that $2\le n\le 2\times 10^5$.