#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "pedefe.in";
const char oname[] = "pedefe.out";

#define FOR(i, a, b)  for (int i = (a); i <= (b); ++ i)
#define FORR(i, b, a) for (int i = (b); i >= (a); -- i)
#define FORi(i, G)    for (vector <int>::iterator i = G.begin(); i != G.end(); ++ i)
#define ALL(X) (X).begin(), (X).end()

#define MAXN	  505
#define MAXVALUE  505

#define modulo 666013

int A[MAXN], B[MAXN], C[MAXN];

int Cnt[2][MAXN][MAXN], Sum[2][MAXN][MAXN], SumV[2][MAXVALUE][MAXN], tSum[MAXN + 1];

vector <int> values[MAXN];


inline void update(int &var, int val) {
	if (val < 0)
		val += modulo;
	else if (val >= modulo)
		val -= modulo;
	if ((var += val) >= modulo)
		var -= modulo;
}

int main(void)
{
	ifstream fin(iname);

	int n, m, p;

	fin >> n >> m >> p;
	FOR (i, 1, n) 
		fin >> A[i];
	FOR (i, 1, m) 
		fin >> B[i];
	FOR (i, 1, p) 
		fin >> C[i];

	fin.close();

	FOR (i, 1, n) {
		FOR (j, 1, i - 1) if (A[j] <= A[i])
			values[i].push_back(A[j]);
		sort(ALL(values[i]));
		values[i].erase(unique(ALL(values[i])), values[i].end());
	}

	int s = 0;
	
	FOR (i, 1, n)
	{
		FORi (it, values[i]) FOR (j, 1, m)
			update(Sum[s][i][j], SumV[s][*it][j]);

		FOR (j, 1, m) if (A[i] == B[j])
		{
			Cnt[s][i][j] = 1;
			update(Cnt[s][i][j], Sum[s][i][1] - Sum[s][i][j]);
		}
		
		memset(tSum, 0, sizeof(tSum));
		FORR (j, m, 1)
			update(tSum[j], Cnt[s][i][j] + tSum[j + 1]);
		FORR (j, m, 1)
			update(SumV[s][A[i]][j], tSum[j]);
	}

	FOR (k, 1, p) 
	{
		s = k & 1;
		memset(Cnt[s], 0, sizeof(Cnt[s])), memset(Sum[s], 0, sizeof(Sum[s])), memset(SumV[s], 0, sizeof(SumV[s]));
		
		FOR (i, 1, n)
		{
			FORi (it, values[i]) FOR (j, 1, m)
				update(Sum[s][i][j], SumV[s][*it][j]);

			FOR (j, 1, m) if (A[i] == B[j]) 
			{
				if (A[i] == C[k])
				{
					if (k == 1)
						Cnt[s][i][j] = 1;
					update(Cnt[s][i][j], Sum[s ^ 1][i][1] - Sum[s ^ 1][i][j]);
				} 
				else
					update(Cnt[s][i][j], Sum[s][i][1] - Sum[s][i][j]);
			}

			memset(tSum, 0, sizeof(tSum));
			FORR (j, m, 1)
				update(tSum[j], Cnt[s][i][j] + tSum[j + 1]);
			FORR (j, m, 1)
				update(SumV[s][A[i]][j], tSum[j]);
		}
	}

	int ret = 0;

	FOR (i, 1, n) FOR (j, 1, m) if (A[i] == B[j]) 
		update(ret, Cnt[p & 1][i][j]);

	ofstream fout(oname);	fout << ret <<'\n';  fout.close();

	return 0;
}