题目描述

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

01211
12099
23300

4

121
214
999

0

数据范围与提示

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