三向投影
时间限制：20s 空间限制：512MB
题目描述
考虑一个由单位立方体构成的立体图形。这个立体图形的底是一个 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 佚名提供