1228_B. Filling the Grid
Suppose there is a h × w grid consisting of empty or full cells. Let's make some definitions:

  * r_{i} is the number of consecutive full cells connected to the left side in the i-th row (1 ≤ i ≤ h). In particular, r_i=0 if the leftmost cell of the i-th row is empty. 
  * c_{j} is the number of consecutive full cells connected to the top end in the j-th column (1 ≤ j ≤ w). In particular, c_j=0 if the topmost cell of the j-th column is empty. 



In other words, the i-th row starts exactly with r_i full cells. Similarly, the j-th column starts exactly with c_j full cells.

<image> These are the r and c values of some 3 × 4 grid. Black cells are full and white cells are empty.

You have values of r and c. Initially, all cells are empty. Find the number of ways to fill grid cells to satisfy values of r and c. Since the answer can be very large, find the answer modulo 1000000007 (10^{9} + 7). In other words, find the remainder after division of the answer by 1000000007 (10^{9} + 7).

Input

The first line contains two integers h and w (1 ≤ h, w ≤ 10^{3}) — the height and width of the grid.

The second line contains h integers r_{1}, r_{2}, …, r_{h} (0 ≤ r_{i} ≤ w) — the values of r.

The third line contains w integers c_{1}, c_{2}, …, c_{w} (0 ≤ c_{j} ≤ h) — the values of c.

Output

Print the answer modulo 1000000007 (10^{9} + 7).

Examples

Input


3 4
0 3 1
0 2 3 0


Output


2


Input


1 1
0
1


Output


0


Input


19 16
16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12
6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4


Output


797922655

Note

In the first example, this is the other possible case.

<image>

In the second example, it's impossible to make a grid to satisfy such r, c values.

In the third example, make sure to print answer modulo (10^9 + 7).
```python
n, m = map(int, input().split())
row = list(map(int, input().split()))
col = list(map(int, input().split()))
grid = [['?'] * m for _ in range(n)]
for i in range(n):
    lng = row[i]
    for j in range(lng):
        grid[i][j] = 'b'
    if lng < m:
        grid[i][lng] = 'w'
for i in range(m):
    lng = col[i]
    for j in range(lng):
        if grid[j][i] != 'w':
            grid[j][i] = 'b'
        else:
            print(0)
            exit(0)
    if lng < n:
        if grid[lng][i] != 'b':
            grid[lng][i] = 'w'
        else:
            print(0)
            exit(0)
comb = 1
for _ in range(sum(map(lambda l: l.count('?'), grid))):
    comb = (comb * 2) % 1000000007
print(comb)

```