#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;

const int NMax = 550;
const int MOD = 666013;

int add(int a, int b) {
	int ret = a + b;
	if (ret >= MOD) ret -= MOD;
	return ret;
}

int main() {
	ifstream cin("pedefe.in");
	ofstream cout("pedefe.out");

	int n, m, p;
	cin >> n >> m >> p;

	vector < int > A[NMax], B[NMax], C(p);
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		A[x].push_back(i);
	}
	for (int i = 1; i <= m; ++i) {
		int x; cin >> x;
		B[x].push_back(i);
	}
	for (int i = 0; i < p; ++i) cin >> C[i];

	vector < vector < int > > DP(n + 5, vector < int > (m + 5));
	vector < vector < int > > upd(n + 5, vector < int > (m + 5));
	
	int idx = 0;
	for (int val = 1; val <= 500; ++val) {
		for (int i = 1; i <= n + 1; ++i) {
			for (int j = 1; j <= m + 1; ++j) {
				upd[i][j] = 0;
			}
		}

		if (idx >= p || C[idx] != val) {
			for (int i = 0; i < (int)A[val].size(); ++i) {
				for (int j = 0; j < (int)B[val].size(); ++j) {
					int pa = A[val][i];
					int pb = B[val][j];
					upd[pa + 1][pb + 1] = add((idx == 0), add(upd[pa + 1][pb + 1], DP[pa][pb]));
				}
			}
			for (int i = 1; i <= n + 1; ++i) {
				for (int j = 1; j <= m + 1; ++j) {
					upd[i][j] = add(upd[i][j], add(upd[i - 1][j], add(MOD - upd[i - 1][j - 1], upd[i][j - 1])));
					DP[i][j] = add(DP[i][j], upd[i][j]);
				}
			}
		} else while (idx < p && C[idx] == val) {
			for (int i = 1; i <= n + 1; ++i) {
				for (int j = 1; j <= m + 1; ++j) {
					upd[i][j] = 0;
				}
			}
			for (int i = 0; i < (int)A[val].size(); ++i) {
				for (int j = 0; j < (int)B[val].size(); ++j) {
					int pa = A[val][i];
					int pb = B[val][j];
					upd[pa + 1][pb + 1] = add(1, add(upd[pa + 1][pb + 1], DP[pa][pb]));
				}
			}
			for (int i = 1; i <= n + 1; ++i) {
				for (int j = 1; j <= m + 1; ++j) {
					upd[i][j] = add(upd[i][j], add(upd[i - 1][j], add(MOD - upd[i - 1][j - 1], upd[i][j - 1])));
					DP[i][j] = upd[i][j];
				}
			}
			++idx;
		}
	}
	cout << DP[n + 1][m + 1];
	return 0;
}