P9768 [ROIR 2021] A+B (Day 2)

**译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day2 T4 [A+B](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。

有三个长为 $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】：所有排列方式均可。 【样例解释2】：我们只计算 $10+20=30$，而不计算 $01+02=03$，因为 $03$ 含前导零。 【样例解释3】：显然有 $10121 + 21909 = 32030$ 与 $12101 + 20919 = 33020$ 两种合法等式，但由于有两个相同的列，所以它们都有两种方式得到答案，总方案数为 $2\times 2=4$。 【数据范围】： 对于所有子任务，有 $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$ |