#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
 
ifstream fi("pedefe.in");
ofstream fo("pedefe.out");
 
const int MOD = 666013, N = 505;
 
vector<vector<int>> dp[2];
int s0[N], s1[N], s2[N];
 
vector<int> alph;
int n, m, p;
 
static inline int add(int a, int b) {
	return (a + b >= MOD ? a + b - MOD : a + b); }

static void enforced(int ch) {
	for (int i = 0; i <= n; ++i)
	for (int j = 0; j <= m; ++j)
		if (s1[i] == s2[j] && s1[i] == ch)
			dp[1][i][j] = dp[0][i - 1][j - 1];
		else
			dp[1][i][j] = 0; 

	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
		dp[1][i][j] = add(dp[1][i][j], add(dp[1][i - 1][j], add(dp[1][i][j - 1], MOD - dp[1][i - 1][j - 1]))); }
 
static void unenforced(int ch, bool pula) {
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j) {
		dp[1][i][j] = add(dp[0][i - 1][j - 1], dp[1][i - 1][j - 1]) * int(s1[i] == s2[j] && s1[i] == ch);
		dp[1][i][j] = add(dp[1][i][j], add(dp[1][i - 1][j], add(dp[1][i][j - 1], MOD - dp[1][i - 1][j - 1]))); }
 
	if (pula)
		return;
 
	for (int i = 0; i <= n; ++i)
	for (int j = 0; j <= m; ++j)
		dp[1][i][j] = add(dp[1][i][j], dp[0][i][j]); }
 
int f[N];
 
int main() {
	int ptr(1);
 
	fi >> n >> m >> p;
	for (int i = 1; i <= n; ++i) {
		fi >> s1[i];
		f[s1[i]] = 1;
		alph.push_back(s1[i]); }
	for (int i = 1; i <= m; ++i) {
		fi >> s2[i];
		if (f[s2[i]])
			f[s2[i]] = 2;
		alph.push_back(s2[i]); }
	for (int i = 1; i <= p; ++i) {
		fi >> s0[i];
		alph.push_back(s0[i]); }
 
	if (!is_sorted(s0 + 1, s0 + p + 1)) {
		fo << "0\n";
		return 0;  }
 
	dp[0] = dp[1] = vector<vector<int>>(n + 5, vector<int>(m + 5));
	sort(begin(alph), end(alph));
	alph.erase(unique(begin(alph), end(alph)), end(alph));
 
	for (auto &line: dp[1])
		fill(begin(line), end(line), 1);
 
	for (int k = 0; k < alph.size(); ++k) {
		if (f[alph[k]] != 2)
			continue;
		swap(dp[0], dp[1]);
		if (alph[k] == s0[ptr]) {
			if (s0[ptr] == s0[ptr + 1]) {
				enforced(alph[k]);
				k-= 1; }
			else
				unenforced(alph[k], true); 
			ptr+= 1; }
		else {
			unenforced(alph[k], false); }
 
		for (int i = 0; i <= n; ++i)
			dp[0][i][0] = 0;
		for (int i = 0; i <= m; ++i)
			dp[0][0][i] = 0; }
 
	cerr << dp[1][n][m] << endl;
	fo << dp[1][n][m] << endl;
 
	return 0; }