题目描述

$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$ で割ったあまりを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $M$ $A_1$ $A_2$ $...$ $A_{N}$ $B_1$ $B_2$ $...$ $B_{M}$

输出格式

条件を満たすような書き込み方の個数を $10^9\ +\ 7$ で割ったあまりを出力せよ．

题目大意

求满足下列条件的 $n\times m$ 的矩阵 $M$ 的个数（$\text{}\bmod 10^9+7$）：

• $1\sim n\times m$ 各出现一次。
• $a_i=\max\limits_{t=1}^m M_{i,t}$。
• $b_j=\max\limits_{t=1}^n M_{t,j}$。

translated by

2 2
4 3
3 4

2

3 3
5 9 7
3 6 9

0

2 2
4 4
4 4

0

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

343772227

提示

制約

• $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$ は整数

Sample Explanation 1

$(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$

Sample Explanation 2

どのような書き込み方をしても条件を満たすことができないので，$0$ を出力します．