Let's consider a permutation P = {$p_{1}$,$ p_{2}$, ..., $p_{N}$} of the set of N = {1, 2, 3, ..., N} elements .  

P is called a magic set if it satisfies both of the following constraints:  

Given a set of K integers, the elements in positions $a_{1}$, $a_{2}$, ..., $a_{K}$ are less than their adjacent elements, i.e., $p_{ai-1} > p_{ai} < p_{ai+1}$
Given a set of L integers, elements in positions $b_{1}$, $b_{2}$, ..., $b_{L}$ are  greater than their adjacent elements, i.e., $p_{bi-1} < p_{bi} > p_{bi+1}$

How many such magic sets are there?

Input Format 

The first line of input contains three integers N, K, L separated by a single space. 

The second line contains K integers, $a_{1}$, $a_{2$}, ... $a_{K}$ each separated by single space. 

the third line contains L integers, $b_{1}$, $b_{2}$, ... $b_{L}$ each separated by single space. 

Output Format 

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

Constraints 

3 <= N <= 5000 

1 <= K, L <= 5000 

2 <= $a_{i}$, $b_{j}$ <= N-1, where i ∈ [1, K] AND j ∈ [1, L]  

Sample Input #00  

4 1 1
2
3

Sample Output #00  

5

Explanation #00

Here, N = 4 $a_{1}$ = 2 and $b_{1}$ = 3. The 5 permutations of {1,2,3,4} that satisfy the condition are 

2 1 4 3
3 2 4 1
4 2 3 1
3 1 4 2
4 1 3 2

Sample Input #01

10 2 2
2 4
3 9

Sample Output #01

161280

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def main():
	(N, K, L) = map(int, input().split())
	K_indices = set(map(int, input().split()))
	L_indices = set(map(int, input().split()))
	done = False
	if len(K_indices & L_indices) > 0:
		done = True
	M = 10 ** 9 + 7
	(Q_12, Q_22) = (0, 0)
	if 2 in K_indices:
		Q_12 = 1
		Q_22 = 0
	elif 2 in L_indices:
		Q_12 = 0
		Q_22 = 1
	else:
		Q_12 = 1
		Q_22 = 1
	prev_Q_partials = {}
	prev_Q_partials[0] = 0
	prev_Q_partials[1] = Q_12
	prev_Q_partials[2] = Q_12 + Q_22
	for j in range(3, N + 1):
		current_Q_partials = {}
		current_Q_partials[0] = 0
		for i in range(1, j + 1):
			if j in K_indices:
				Q_ij = 0
				if j - 1 in K_indices:
					done = True
					break
				else:
					Q_ij = (prev_Q_partials[j - 1] - prev_Q_partials[i - 1]) % M
			elif j in L_indices:
				if j - 1 in L_indices:
					done = True
					break
				Q_ij = prev_Q_partials[i - 1] % M
			elif j - 1 in K_indices:
				Q_ij = prev_Q_partials[i - 1] % M
			elif j - 1 in L_indices:
				Q_ij = (prev_Q_partials[j - 1] - prev_Q_partials[i - 1]) % M
			else:
				Q_ij = prev_Q_partials[j - 1] % M
			current_Q_partials[i] = (current_Q_partials[i - 1] + Q_ij) % M
		prev_Q_partials = current_Q_partials
		if done:
			break
	if done:
		print(0)
	else:
		print(current_Q_partials[N] % M)
main()


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


(n, k, p) = (int(x) for x in input().split())
A = [int(x) - 1 for x in input().split()]
B = [int(x) - 1 for x in input().split()]
direction = [0] * (n + 1)
m = 1000000007
bad_const = False
for x in A:
	if direction[x] == -1 or direction[x + 1] == 1:
		bad_const = True
	direction[x] = 1
	direction[x + 1] = -1
for x in B:
	if direction[x] == 1 or direction[x + 1] == -1:
		bad_const = True
	direction[x] = -1
	direction[x + 1] = 1
if bad_const:
	print(0)
else:
	current = [0] * n
	current[0] = 1
	for i in range(1, n):
		update = [0] * n
		d = direction[i]
		if d == 0:
			s = sum(current) % m
			for j in range(i + 1):
				update[j] = s
		if d == 1:
			update[i] = 0
			for j in range(i - 1, -1, -1):
				update[j] = (update[j + 1] + current[j]) % m
		if d == -1:
			update[0] = 0
			for j in range(1, i + 1):
				update[j] = (update[j - 1] + current[j - 1]) % m
		current = update[:]
print(sum(current) % m)


def extremum_permutations(N, less, more):
	fromj = [1, 0]
	tillj = [0, 1]
	total = 1
	for i in range(1, N):
		if less[i] and more[i]:
			return 0
		if less[i]:
			dp = [tillj[j] % 1000000007 for j in range(i + 1)]
		elif more[i]:
			dp = [fromj[j] % 1000000007 for j in range(i + 1)]
		else:
			dp = [total % 1000000007 for j in range(i + 1)]
		total = sum(dp)
		f = total % 1000000007
		t = 0
		fromj = [total]
		tillj = [0]
		for j in range(i + 1):
			f -= dp[j]
			f = f % 1000000007
			fromj.append(f)
			t += dp[j]
			t = t % 1000000007
			tillj.append(t)
	return sum(dp) % 1000000007
(N, K, L) = map(int, input().strip().split(' '))
ks = list(map(int, input().strip().split(' ')))
ls = list(map(int, input().strip().split(' ')))
less = [False for i in range(N)]
more = [False for i in range(N)]
for k in ks:
	less[k - 1] = True
	more[k] = True
for l in ls:
	more[l - 1] = True
	less[l] = True
print(extremum_permutations(N, less, more))


(n, la, lb) = map(int, input().split(' '))
(F, M) = ([0] * (n + 2), 10 ** 9 + 7)
for a in map(int, input().split(' ')):
	if F[a - 1] == 1 or F[a + 1] == 1:
		M = None
	F[a] = 1
for b in map(int, input().split(' ')):
	if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
		M = None
	F[b] = -1
if M == None:
	print(0)
else:
	(A, B, FF) = ([0] * (n + 1), [0] * (n + 1), [None] * (n + 1))
	for i in range(1, n + 1):
		FF[i] = F[i] - F[i - 1]
	A[1] = 1
	for i in range(2, n + 1):
		for j in range(1, i + 1):
			if FF[i] > 0:
				B[j] = (B[j - 1] + A[j - 1]) % M
			elif FF[i] < 0:
				B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % M
			else:
				B[j] = (B[j - 1] + A[i - 1]) % M
		(A, B) = (B, A)
	print(A[n])


def main():
	(N, K, L) = map(int, input().split())
	K_indices = set(map(int, input().split()))
	L_indices = set(map(int, input().split()))
	done = False
	if len(K_indices & L_indices) > 0:
		done = True
	M = 10 ** 9 + 7
	(Q_12, Q_22) = (0, 0)
	if 2 in K_indices:
		Q_12 = 1
		Q_22 = 0
	elif 2 in L_indices:
		Q_12 = 0
		Q_22 = 1
	else:
		Q_12 = 1
		Q_22 = 1
	prev_Q_partials = {}
	prev_Q_partials[0] = 0
	prev_Q_partials[1] = Q_12
	prev_Q_partials[2] = Q_12 + Q_22
	for j in range(3, N + 1):
		current_Q_partials = {}
		current_Q_partials[0] = 0
		for i in range(1, j + 1):
			if j in K_indices:
				Q_ij = 0
				if j - 1 in K_indices:
					done = True
					break
				else:
					Q_ij = (prev_Q_partials[j - 1] - prev_Q_partials[i - 1]) % M
			elif j in L_indices:
				if j - 1 in L_indices:
					done = True
					break
				Q_ij = prev_Q_partials[i - 1] % M
			elif j - 1 in K_indices:
				Q_ij = prev_Q_partials[i - 1] % M
			elif j - 1 in L_indices:
				Q_ij = (prev_Q_partials[j - 1] - prev_Q_partials[i - 1]) % M
			else:
				Q_ij = prev_Q_partials[j - 1] % M
			current_Q_partials[i] = (current_Q_partials[i - 1] + Q_ij) % M
		prev_Q_partials = current_Q_partials
		if done:
			break
	if done:
		print(0)
	else:
		print(current_Q_partials[N] % M)
main()


def extremum_permutations(N, less, more):
	fromj = [1, 0]
	tillj = [0, 1]
	total = 1
	for i in range(1, N):
		if less[i] and more[i]:
			return 0
		if less[i]:
			dp = [tillj[j] % 1000000007 for j in range(i + 1)]
		elif more[i]:
			dp = [fromj[j] % 1000000007 for j in range(i + 1)]
		else:
			dp = [total % 1000000007 for j in range(i + 1)]
		total = sum(dp)
		f = total % 1000000007
		t = 0
		fromj = [total]
		tillj = [0]
		for j in range(i + 1):
			f -= dp[j]
			f = f % 1000000007
			fromj.append(f)
			t += dp[j]
			t = t % 1000000007
			tillj.append(t)
	return sum(dp) % 1000000007
(N, K, L) = map(int, input().strip().split(' '))
ks = list(map(int, input().strip().split(' ')))
ls = list(map(int, input().strip().split(' ')))
less = [False for i in range(N)]
more = [False for i in range(N)]
for k in ks:
	less[k - 1] = True
	more[k] = True
for l in ls:
	more[l - 1] = True
	less[l] = True
print(extremum_permutations(N, less, more))


import os
import sys
from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
dir = [0] * (N + 1)
for i in mins:
	if dir[i - 1] == UP or dir[i] == DOWN:
		print('0')
		sys.exit(0)
	dir[i - 1] = DOWN
	dir[i] = UP
for i in maxs:
	if dir[i - 1] == DOWN or dir[i] == UP:
		print('0')
		sys.exit(0)
	dir[i - 1] = UP
	dir[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if dir[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif dir[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif dir[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import math
import os
import random
import re
import sys
import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import math
import os
import random
import re
import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


import math
import os
import random
import re
import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import math
import os
import random
import re
import sys

def extremum_permutations(N, less, more):
	fromj = [1, 0]
	tillj = [0, 1]
	total = 1
	for i in range(1, N):
		if less[i] and more[i]:
			return 0
		if less[i]:
			dp = [tillj[j] % 1000000007 for j in range(i + 1)]
		elif more[i]:
			dp = [fromj[j] % 1000000007 for j in range(i + 1)]
		else:
			dp = [total % 1000000007 for j in range(i + 1)]
		total = sum(dp)
		f = total % 1000000007
		t = 0
		fromj = [total]
		tillj = [0]
		for j in range(i + 1):
			f -= dp[j]
			f = f % 1000000007
			fromj.append(f)
			t += dp[j]
			t = t % 1000000007
			tillj.append(t)
	return sum(dp) % 1000000007
(N, K, L) = map(int, input().strip().split(' '))
ks = list(map(int, input().strip().split(' ')))
ls = list(map(int, input().strip().split(' ')))
less = [False for i in range(N)]
more = [False for i in range(N)]
for k in ks:
	less[k - 1] = True
	more[k] = True
for l in ls:
	more[l - 1] = True
	less[l] = True
print(extremum_permutations(N, less, more))


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import math
import os
import random
import re
import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
qwe = 10 ** 9 + 7

def permcount(permlen, h, b):
	if any((x + 1 == y for c in map(sorted, (h, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(h) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((h, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % qwe for elt in count]
	return sum(count) % qwe

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
h = readints()
b = readints()
assert len(h) == alen and len(b) == blen
print(permcount(permlen, h, b))


import math
import os
import random
import re
import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


import sys
(N, K, L) = map(int, input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1000000000.0 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
	if direction[i - 1] == UP or direction[i] == DOWN:
		print('0')
		sys.exit(0)
	direction[i - 1] = DOWN
	direction[i] = UP
for i in maxs:
	if direction[i - 1] == DOWN or direction[i] == UP:
		print('0')
		sys.exit(0)
	direction[i - 1] = UP
	direction[i] = DOWN
f = []
for i in range(N + 1):
	f.append([0] * (N + 1))

def interval(a, b):
	if a <= b:
		return range(a, b + 1)
	else:
		return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
	if direction[i] == UP:
		f[i][0] = 0
		for n in interval(1, N - i):
			f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
	elif direction[i] == DOWN:
		f[i][N - i] = 0
		for n in interval(N - i - 1, 0):
			m = N - i - n
			f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
	elif direction[i] == ANY:
		s = 0
		for k in interval(0, N - (i + 1)):
			s += f[i + 1][k]
			s %= M
		for n in interval(0, N - i):
			f[i][n] = s
	i -= 1
ret = 0
for k in interval(0, N - 1):
	ret += f[1][k]
	ret %= M
print(ret)


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))


from itertools import islice, accumulate
MOD = 10 ** 9 + 7

def permcount(permlen, a, b):
	if any((x + 1 == y for c in map(sorted, (a, b)) for (x, y) in zip(c, c[1:]))):
		return 0
	if set(a) & set(b):
		return 0
	goingup = [None] * permlen
	for (c, low) in ((a, True), (b, False)):
		for elt in c:
			elt -= 1
			if elt > 0:
				goingup[elt] = not low
			if elt < permlen - 1:
				goingup[elt + 1] = low
	count = [1]
	for (i, inc) in islice(enumerate(goingup), 1, permlen):
		if inc is None:
			count = [sum(count)] * (i + 1)
		elif inc:
			count = [0] + list(accumulate(count))
		else:
			count = list(reversed(list(accumulate(reversed(count))))) + [0]
		count = [elt % MOD for elt in count]
	return sum(count) % MOD

def readints():
	return [int(f) for f in input().split()]
(permlen, alen, blen) = readints()
a = readints()
b = readints()
assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))