/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 行 M 列のグリッドに，1 から N \times M までの整数を重複のないように 1 つずつ書き込むことを考えます． ここで，普通に書き込むのでは面白くないと思った高橋君は，以下の条件を満たすように数を書き込むことにしました．
- i 行目に書き込まれている値のうち，最大の値は A_i (1 \leq i \leq N)
- j 列目に書き込まれている値のうち，最大の値は B_j (1 \leq j \leq M)
高橋君のために，この条件を満たすような書き込み方の個数を 10^9 + 7 で割ったあまりを求めてください．
制約
- 1 \leq N \leq 1000
- 1 \leq M \leq 1000
- 1 \leq A_i \leq N \times M
- 1 \leq B_j \leq N \times M
- A_i, B_j は整数
入力
入力は以下の形式で標準入力から与えられる．
N M
A_1 A_2 ... A_{N}
B_1 B_2 ... B_{M}
出力
条件を満たすような書き込み方の個数を 10^9 + 7 で割ったあまりを出力せよ．
入力例 1
2 2 4 3 3 4
出力例 1
2
(A_1, A_2) = (4, 3)，(B_1, B_2) = (3, 4) であり，この場合は以下の 2 通りの書き込み方があります．
- 1 行 1 列目に 1，1 行 2 列目に 4，2 行 1 列目に 3，2 行 2 列目に 2
- 1 行 1 列目に 2，1 行 2 列目に 4，2 行 1 列目に 3，2 行 2 列目に 1
入力例 2
3 3 5 9 7 3 6 9
出力例 2
0
どのような書き込み方をしても条件を満たすことができないので，0 を出力します．
入力例 3
2 2 4 4 4 4
出力例 3
0
入力例 4
14 13 158 167 181 147 178 151 179 182 176 169 180 129 175 168 181 150 178 179 167 180 176 169 182 177 175 159 173
出力例 4
343772227
Score : 500 points
Problem Statement
Consider writing each of the integers from 1 to N \times M in a grid with N rows and M columns, without duplicates. Takahashi thinks it is not fun enough, and he will write the numbers under the following conditions:
- The largest among the values in the i-th row (1 \leq i \leq N) is A_i.
- The largest among the values in the j-th column (1 \leq j \leq M) is B_j.
For him, find the number of ways to write the numbers under these conditions, modulo 10^9 + 7.
Constraints
- 1 \leq N \leq 1000
- 1 \leq M \leq 1000
- 1 \leq A_i \leq N \times M
- 1 \leq B_j \leq N \times M
- A_i and B_j are integers.
Input
Input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_{N}
B_1 B_2 ... B_{M}
Output
Print the number of ways to write the numbers under the conditions, modulo 10^9 + 7.
Sample Input 1
2 2 4 3 3 4
Sample Output 1
2
(A_1, A_2) = (4, 3) and (B_1, B_2) = (3, 4). In this case, there are two ways to write the numbers, as follows:
- 1 in (1, 1), 4 in (1, 2), 3 in (2, 1) and 2 in (2, 2).
- 2 in (1, 1), 4 in (1, 2), 3 in (2, 1) and 1 in (2, 2).
Here, (i, j) denotes the square at the i-th row and the j-th column.
Sample Input 2
3 3 5 9 7 3 6 9
Sample Output 2
0
Since there is no way to write the numbers under the condition, 0 should be printed.
Sample Input 3
2 2 4 4 4 4
Sample Output 3
0
Sample Input 4
14 13 158 167 181 147 178 151 179 182 176 169 180 129 175 168 181 150 178 179 167 180 176 169 182 177 175 159 173
Sample Output 4
343772227