题目描述

译自 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$。

123
123
246

6

所有排列方式均可。

01
02
03

1

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

01211
12099
23300

4

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

121
214
999

0

数据范围与提示

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