#3347. Srm524 Axonometric Projection

内存限制:128 MiB 时间限制:3 Sec

题目描述

让我们来考虑一个单位立方体建成的模型,这个建筑的底是一个N*M
的单位正方形网格,在每个正方体上面堆着若干个,可能为0,个单位
立方体,每个立方体属于其中一个立方体堆
现给出一个建筑的左视图的正视图,请计算有多少种建筑符合给出的
条件。答案可能很大,请Mod 10^9+9

输入格式

第一行是整数N,第一个描述建筑的左视图,第i个数表示了由上向下
看时第i行最高的立方体堆的高度,第三行是整数M,第四行描述建筑
的正视图,第i个数表示了由上向下看时第i列最高的立方体堆的高度

输出格式

如题

样例

样例输入


			
2
1 1
2
1 1

样例输出


			
7

数据范围与提示

对于100%的数据,1 <= n,m <= 50,所有出现的数不超过10^4。