Lost Table

Time limit2sMemory limit2048 MB

Summary

Count the n by m tables of positive integers whose row maxima are a and column maxima are b, modulo 1e9+7.

Level: Hard8 of 10
Topics: Combinatorics, Math, Sorting
Solved: No attempts yet

Problem

Er-Tostik had a table of size $n \times m$ filled with positive integers. Aldar-Kose stole the table as a prank and told Er-Tostik only the maximum value of each row and each column. Aldar-Kose will return the table only if Er-Tostik can count how many different tables have these row and column maxima. The count can be very large, so output it modulo $10^9 + 7$ . Help Er-Tostik get his table back.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n, m \leq 2 \cdot 10^5$ ), the dimensions of the table. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ), the maximum values of the rows. The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ( $1 \leq b_j \leq 10^9$ ), the maximum values of the columns.

Output

Print one integer: the number of tables that satisfy the conditions, modulo $10^9 + 7$ . If no table matches the given maxima, print 0.

Examples5

Example 1
Input
```
3 3
2 2 3
2 3 3
```
Expected output
```
89
```
Example 2
Input
```
1 1
1
2
```
Expected output
```
0
```
Example 3
Input
```
5 5
2 2 3 3 3
2 2 2 3 3
```
Expected output
```
49049891
```

Example 4

Input

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

Expected output

808346164

Example 5
Input
```
2 3
2 3
3 1 5
```
Expected output
```
0
```