让我们来考虑一个单位立方体建成的模型,这个建筑的底是一个 n×mn\times mn×m 的单位正方形网格,在每个正方体上面堆着若干个(可能为 000 个)单位立方体,每个立方体属于其中一个立方体堆.现给出一个建筑的左视图和正视图,请计算有多少种建筑符合给出的条件.答案可能很大,请输出答案模 109+910^9+9109+9 的结果,
第一行是整数 nnn.第二行 nnn 个整数描述建筑的左视图,第 iii 个数表示了从左向右看时第 iii 行最高的立方体堆的高度.第三行是整数 mmm.第四行 mmm 个数描述建筑的正视图,第 iii 个数表示了从前向后看时第 iii 列最高的立方体堆的高度.
输出一行一个整数,表示答案模 109+910^9+9109+9 的结果.