题目描述

让我们来考虑一个单位立方体建成的模型,这个建筑的底是一个 n×mn\times m 的单位正方形网格,在每个正方体上面堆着若干个(可能为 00 个)单位立方体,每个立方体属于其中一个立方体堆。现给出一个建筑的左视图和正视图,请计算有多少种建筑符合给出的条件。答案可能很大,请输出答案模 109+910^9+9 的结果,

输入格式

第一行是整数 nn。第二行 nn 个整数描述建筑的左视图,第 ii 个数表示了从左向右看时第 ii 行最高的立方体堆的高度。第三行是整数 mm。第四行 mm 个数描述建筑的正视图,第 ii 个数表示了从前向后看时第 ii 列最高的立方体堆的高度。

输出格式

输出一行一个整数,表示答案模 109+910^9+9 的结果。

2
1 1 
2
1 1 
7

数据规模与约定

对于 100%100\% 的数据,保证 1n,m501 \leq n,m \leq 50,所有出现的数不超过 10410^4

1 条评论

  • 1

信息

ID
3347
时间
1000ms
内存
256MiB
难度
10
标签
(无)
递交数
3
已通过
1
上传者