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

01
02
03

1

01211
12099
23300

4

121
214
999

0

Constraints

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