题目描述

考虑三个用十进制表示的非负整数 $a,b,c$。它们的长度相同，均为 $n$ 位，并且原始输入中允许有前导零。

将这三个数按位上下对齐写成三行，共 $n$ 列。例如：

01211
12099
23300

现在要求重新排列这些列，使得重新排列后满足：

$$a+b=c.$$

在重新排列后，得到的 $a,b,c$ 不允许有前导零。

请问有多少种不同的列排列方式满足要求？

列排列方式按排列本身区分，即使交换两个完全相同的列后得到的三行数字没有变化，也认为这是两种不同的排列方式。例如，上面例子中若交换最后两列，虽然这两列数字完全相同，但仍算作不同的列排列。

由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入三行，分别表示整数 $a,b,c$。

每个数都由 $n$ 个十进制数字组成，并且可以以 0 开头。

输出格式

输出一个整数，表示满足条件的列排列数量对 $10^9+7$ 取模后的结果。

数据范围

$$2\le n\le 2\cdot 10^5.$$

子任务

子任务	分值	附加限制	依赖子任务	反馈信息
1	7	$2\le n\le 6$	-	第一处错误
2	14	$2\le n\le 18$	1
3	15	$2\le n\le 200$，没有数字 0	-
4	5	$2\le n\le 200$	1-3
5	17	$2\le n\le 750$，没有数字 0	3
6	5	$2\le n\le 750$	1-5
7	20	$2\le n\le 2\cdot 10^5$，没有数字 0	3,5
8	17	$2\le n\le 2\cdot 10^5$	1-7

样例 1 输入

123
123
246

样例 1 输出

6

样例 2 输入

01
02
03

样例 2 输出

1

样例 3 输入

01211
12099
23300

样例 3 输出

4

样例 4 输入

121
214
999

样例 4 输出

0

样例解释

样例 1 中，所有列排列都满足条件。

样例 2 中，唯一合法的排列对应：

10 + 20 = 30

而

01 + 02 = 03

因为有前导零，所以不合法。

样例 3 中，可能得到：

10121 + 21909 = 32030

以及

12101 + 20919 = 33020

并且每种结果都可以由两种不同的列排列得到，因此答案为 $4$。