잃어버린 표

시간 제한2초메모리 제한2048 MB

요약

양의 정수로 이루어진 n×m 표 가운데 행 최댓값이 a, 열 최댓값이 b인 표의 개수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 조합론, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

Er-Tostik은 양의 정수가 들어 있는 $n \times m$ 크기의 표를 가지고 있었다. Aldar-Kose는 장난으로 그 표를 훔치고, 각 행과 각 열의 최댓값만 Er-Tostik에게 알려 주었다. Er-Tostik이 이 행과 열의 최댓값을 만족하는 서로 다른 표가 몇 개인지 세면 Aldar-Kose가 표를 돌려준다. 개수가 매우 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 출력한다. Er-Tostik이 표를 되찾도록 도와라.

입력

첫째 줄에 표의 크기를 나타내는 두 정수 $n$ 과 $m$ 이 주어진다 ( $1 \leq n, m \leq 2 \cdot 10^5$ ). 둘째 줄에는 각 행의 최댓값 $a_1, a_2, \ldots, a_n$ 이 주어진다 ( $1 \leq a_i \leq 10^9$ ). 셋째 줄에는 각 열의 최댓값 $b_1, b_2, \ldots, b_m$ 이 주어진다 ( $1 \leq b_j \leq 10^9$ ).

출력

조건을 만족하는 표의 개수를 $10^9 + 7$ 로 나눈 나머지를 한 줄에 출력한다. 주어진 최댓값을 만족하는 표가 없으면 0을 출력한다.

예제5

예제 1
입력
```
3 3
2 2 3
2 3 3
```
예상 출력
```
89
```
예제 2
입력
```
1 1
1
2
```
예상 출력
```
0
```
예제 3
입력
```
5 5
2 2 3 3 3
2 2 2 3 3
```
예상 출력
```
49049891
```

예제 4

입력

12 13
2 2 2 3 3 4 4 4 4 5 5 5
2 3 3 3 3 4 5 5 5 5 5 5 5

예상 출력

808346164

예제 5
입력
```
2 3
2 3
3 1 5
```
예상 출력
```
0
```