Fill the grid

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk has arrays \(l\) and \(r\) of length \(n\), all values of these arrays are from \(0\) to \(m\), and also an array \(d\) of length \(m\), all values of which are from \(0\) to \(n\).

Marichka can rearrange the elements in each array in any way. Also Zenyk has a grid of size \(n \times m\), divided into unit cells, all cells of which are initially white. After that, Zenyk paints the first \(l_i\) cells and the last \(r_i\) cells in the \(i\)-th row blue. And Zenyk also paints the bottom \(d_j\) cells in the \(j\)-th column blue.

Zenyk wants to completely paint the entire grid, but without using too much paint, and therefore paint each cell exactly once. Marichka is interested in how many ways there are to rearrange the values in each of the arrays to achieve this. Two ways are considered different if there is at least one index of at least one array such that the corresponding values differ. Since the number of ways can be very large, output the remainder of the number of ways modulo \(10^9+7\).

Input

The first line contains \(2\) integers \(n\) and \(m\).

The second line contains \(n\) integers \(l_i\).

The third line contains \(n\) integers \(r_i\).

The fourth line contains \(m\) integers \(d_i\).

Output

Output a single integer – the remainder of the number of ways modulo \(10^9+7\).

Constraints

\(1 \le n, m \le 2 \cdot 10^5\),

\(0 \le l_i, r_i \le m\),

\(0 \le d_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 4 0 1 2 0 1 1 1 1 2 3	1

Input (stdin) сopy	Output (stdout) сopy
4 7 4 4 0 0 3 3 7 7 0 0 0 0 0 0 0	6

Input (stdin) сopy	Output (stdout) сopy
1 1 1 0 1	0

Notes

The only way of coloring in the first example:

In the second example, there are \(6\) ways to rearrange the values in the array \(l\), for each of them there is a single variant of the arrays \(r\) and \(d\).

In the third example, it is impossible to fulfill the condition, because a cell will be painted twice.