問題１ - 問題２ - 問題３ - 問題４ - 問題５ - 問題６
NPCA(North Park Crazy Athletic)という新しい遊具が近所の公園に作られたため、太郎君は遊んでみることにした。
この遊具の構造は非常に簡単なものである。
・東西方向の辺が W m、南北方向の辺が H mの長方形の形をしたフィールドが一辺 1 mの正方形の形をした区画に分割されていて、各区画には底辺が一辺 1 mの正方形である直方体の形をしたブロックがひとつずつ置いてある。
・高さが 1 から W×H までの整数であるブロックがひとつずつある。つまり、ブロックは全部で W×H 個あることになる。
この遊具を制覇するには、ブロックの配置を把握することが必要である。
そのために太郎君は、各列・各行で一番高いブロックの高さを調べた。
そして、条件を満たすブロックの配置が何通りあるのかを計算することにした。
例えば、Sample input 1の場合は下図のような２通りの配置が考えられる。
１行目には、W, H が空白を区切りとして書かれている。
２行目には、各列で一番高いブロックの高さを表す 1,000,000 を超えない W個の自然数が空白を区切りとして書かれている。
３行目には、各行で一番高いブロックの高さを表す 1,000,000 を超えない H個の自然数が空白を区切りとして書かれている。
条件を満たすブロックの配置が個数を「1,000,000,007で割った余り」を１行に出力せよ。
ただし、条件を満たすブロックの配置が存在しない場合は 0 を出力せよ。
1 ≦ W, H ≦ 1000
ーSample input 1ー
2 2
4 2
3 4
ーSample output 1ー
2
ーSample input 2ー
1 1
1
2
ーSample output 2ー
0
ーSample input 3ー
3 2
3 6 4
5 6
ーSample output 3ー
8