7902: BZOJ3902:三向投影

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

考虑一个由单位立方体构成的立体图形。这个立体图形的底是一个 n 行 m 列的单位平方网 格。每一个单位平方格竖直向上都直立着一些单位立方体(有可能为空)。这个立体图形中每个 单位立方体都属于其竖直向下投影到的单位平方格。每个单位立方体不能架空(即要么底部和另 一个单位立方体接触,要么与底接触)。 你将得到这个立体图形的左视图 (Left View) 和主视图 (Front View),求可能的立体图形数。 下图对应了 n =4;m =5 的一个合法立体图形。


输入格式

第一行为 n,m。 第二行为 n 个整数,对应左视图,即每一行的最大高度。 第三行为 m 个整数,对应主视图,即每一列的最大高度。


输出格式

一个数,为可能的立体图形数的个数模 10^9 +9。


样例输入

4 5
5 2 4 1
5 2 4 0 1

样例输出

429287

提示

对于 100% 的数据,1 <= n;m <= 50; 每行每列最大高度不超过 10000。


题目来源

By 佚名提供

加入题单

上一题 下一题 算法标签: