题目描述

译自 ROIR 2021 Day2 T4 A+B。

有三个长为 $n$ 的可能含前导零的整数 $a, b, c$，按如下方式排成三行 $n$ 列：

$a$
$b$
$c$

问，有多少种不同的列的排列方式，使得被横着念出来的三个整数 $x, y, z$ 有 $x + y = z$ 成立且三个整数均没有前导零。排列方式的个数可能很多，输出其 $\bmod 10^9 + 7$ 即可。

---

输入格式

第一行为一个长 $n$ 的整数 $a$。

第二行为一个长 $n$ 的整数 $b$。

第三行为一个长 $n$ 的整数 $c$。

---

输出格式

仅一行一个整数，表示不同的排列方式的个数模 $10^9+7$。

---

样例

样例 1

输入

123
123
246

输出

6

所有排列方式均可。

样例 2

输入

01
02
03

输出

1

我们只计算 $10+20=30$，而不计算 $01+02=03$，因为 $03$ 含前导零。

样例 3

输入

01211
12099
23300

输出

4

显然有 $10121 + 21909 = 32030$ 与 $12101 + 20919 = 33020$ 两种合法等式，但由于有两个相同的列，所以它们都有两种方式得到答案，总方案数为 $2 \times 2 = 4$。

样例 4

输入

121
214
999

输出

0

---

数据范围与提示

对于所有子任务，有 $2 \le n \le 2 \times 10^5$。

子任务编号	特殊限制	分值
1	$n \le 6$	7
2	$n \le 18$	14
3	$n \le 200$，读入的数字中不含 $0$	15
4	$n \le 200$	5
5	$n \le 750$，读入的数字中不含 $0$	17
6	$n \le 750$	5
7	读入的数字中不含 $0$	20
8	无特殊限制	17