#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define set(x,y) memset(x,y,sizeof(x))
#define cpy(x,y) memcpy(x,y,sizeof(x))

typedef long long LL;
typedef __int128 LLL;
typedef unsigned long long ULL;
typedef double D;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<D,D> PDD;

const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+9;
const int N=205;

int n,m;
int a[N],b[N];
int mxa[N],mxb[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		if(!a[i]) --i,--n;
	}
	for(int i=1;i<=m;++i){
		scanf("%d",b+i);
		if(!b[i]) --i,--m;
	}
	int ans=0;
	for(int s=0;s<1<<n+m;++s){
		int cnt=0,res=1;
		for(int i=0;i<n+m;++i)
			if(s>>i&1){
				++cnt;
				if(i<n) --a[i+1];
				else --b[i-n+1];
			}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				res=(LL)res*(min(a[i],b[j])+1)%mod;
		for(int i=0;i<n+m;++i)
			if(s>>i&1){
				if(i<n) ++a[i+1];
				else ++b[i-n+1];
			}
		if(cnt&1) ans=(ans+mod-res)%mod;
		else ans=(ans+res)%mod;
	}
	printf("%d\n",ans);
	return 0;
}