B. Filling the Grid_牛客博客

input

standard input

output

standard output

Suppose there is a h×wh×w grid consisting of empty or full cells. Let's make some definitions:

riri is the number of consecutive full cells connected to the left side in the ii-th row (1≤i≤h1≤i≤h). In particular, ri=0ri=0 if the leftmost cell of the ii-th row is empty.
cjcj is the number of consecutive full cells connected to the top end in the jj-th column (1≤j≤w1≤j≤w). In particular, cj=0cj=0 if the topmost cell of the jj-th column is empty.

In other words, the ii-th row starts exactly with riri full cells. Similarly, the jj-th column starts exactly with cjcj full cells.

These are the rr and cc values of some 3×43×4 grid. Black cells are full and white cells are empty.

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

Input

The first line contains two integers hh and ww (1≤h,w≤1031≤h,w≤103) — the height and width of the grid.

The second line contains hh integers r1,r2,…,rhr1,r2,…,rh (0≤ri≤w0≤ri≤w) — the values of rr.

The third line contains ww integers c1,c2,…,cwc1,c2,…,cw (0≤cj≤h0≤cj≤h) — the values of cc.

Output

Print the answer modulo 1000000007(109+7)1000000007(109+7).

Examples

input

Copy

3 4
0 3 1
0 2 3 0

output

Copy

input

Copy

1 1
0
1

output

Copy

input

Copy

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

Copy

797922655

Note

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

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

In the third example, make sure to print answer modulo (109+7)(109+7).

代码：

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long r[1005];
long long c[1005],h,w;
int a[1005][1005]={0};
long long s=0;
int main()
{
	cin>>h>>w;
	for(int i=1;i<=h;i++)
	cin>>r[i];
	for(int j=1;j<=w;j++)
	cin>>c[j];
	int fl=1;
	for(int i=1;i<=h;i++)
	{
		if(fl==0)
		break;
		for(int j=1;j<r[i]+2&&j<=w;j++)
		{
			if(j<=r[i])
			{
				if(a[i][j]>=0)
				a[i][j]=1;
				else
				{
					fl=0;
					break;
				}
			}
			if(j==r[i]+1)
			{
				if(a[i][j]==1)
				{
					fl=0;
					break;
				}
				else
				a[i][j]=-1;
			}
		}
	}
	for(int i=1;i<=w;i++)
	{
		if(fl==0)
		break;
		for(int j=1;j<c[i]+2&&j<=h;j++)
		{
			if(j<=c[i])
			{
				if(a[j][i]>=0)
				a[j][i]=1;
				else
				{
					fl=0;
					break;
				}
			}
			if(j==c[i]+1)
			{
				if(a[j][i]==1)
				{
					fl=0;
					break;
				}
				else
				a[j][i]=-1;
			}
		}
	}
	if(fl==0)
	{
		cout<<0;
	}
	else
	{
		s=1;
		for(int i=1;i<=h;i++)
		{
			for(int j=1;j<=w;j++)
			{
				if(a[i][j]==0)
				{
					s=s*2;
					s=s%mod;
				}
			}
		}
		cout<<s%mod;
	}
	
}