#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;
 
template<int MOD>
class Num {
public:
	int val;
 
	Num() {
		val = 0; };
	Num(int _val) {
		val = _val % MOD;
		val = val < 0 ? val + MOD : val; }
 
	inline Num operator + (const Num &arg) const {
		Num res;
		res.val = val + arg.val;
		res.val = res.val >= MOD ? res.val - MOD : res.val;
		return res; }
 
	inline Num operator - (const Num &arg) const {
		Num res;
		res.val = val - arg.val;
		res.val = res.val < 0 ? res.val + MOD : res.val;
		return res; }
 
	inline Num operator - () const {
		Num res;
		res.val = MOD - res.val;
		res.val = res.val == MOD ? 0 : res.val;
		return res; }
 
	inline void operator += (const Num &arg) {
		(*this) = (*this) + arg; }
 
	inline void operator -= (const Num &arg) {
		(*this) = (*this) - arg; }
 
	inline void operator *= (const Num &arg) {
		(*this) = (*this) * arg; } };
 
template<int MOD>
ostream &operator << (ostream &fo, const Num<MOD> &c) {
	fo << c.val;
	return fo; }
 
template<int MOD>
istream &operator >> (istream &fi, Num<MOD> &c) {
	fi >> c.val;
	c = Num<MOD>(c.val);
	return fi; }
 
 
vector<vector<Num<MOD>>> dp[2];
int s0[N], s1[N], s2[N];
 
vector<int> alph;
int n, m, p;
 
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].val = 0;
 
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
		dp[1][i][j]+= dp[1][i - 1][j] + dp[1][i][j - 1] - 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) {
		if (s1[i] == s2[j] && s1[i] == ch)
			dp[1][i][j] = dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1];
		else
			dp[1][i][j].val = 0;
		dp[1][i][j]+= dp[1][i - 1][j] + dp[1][i][j - 1] - 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]+= 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<Num<MOD>>>(n + 5, vector<Num<MOD>>(m + 5));
	sort(begin(alph), end(alph));
	alph.erase(unique(begin(alph), end(alph)), end(alph));
 
	for (auto &line: dp[1])
		for (auto &i: line)
			i.val = 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].val = 0;
		for (int i = 0; i <= m; ++i)
			dp[0][0][i].val = 0; }
 
	cerr << dp[1][n][m] << endl;
	fo << dp[1][n][m] << endl;
 
	return 0; }