#include <fstream>
#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 lastbit(x) ((x) ^ ((x) & ((x) - 1)))

#define MAXN	  505
#define MAXVALUE  505

#define modulo 666013

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

int Sum[2][MAXN][MAXN], SumV[2][MAXVALUE][MAXN];


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

int query(int M[][MAXN], int i, int j) 
{
	int ret = 0;
	for (; i > 0; i -= lastbit(i))
		if ((ret += M[i][j]) >= modulo)
			ret -= modulo;
	return ret;
}

void update(int M[][MAXN], int i, int j, int val) 
{
	for (; i < MAXVALUE; i += lastbit(i))
		if ((M[i][j] += val) >= modulo)
			M[i][j] -= modulo;
}

int main(void)
{
	int n, m, p;
	int Cnt[MAXN];

	ifstream fin(iname);

	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();

	int r = 0, ret = 0;
	
	FOR (i, 1, n)
	{
		FOR (j, 1, m)
			Sum[r][i][j] = query(SumV[r], A[i], j);

		memset(Cnt, 0, sizeof(Cnt));
		FOR (j, 1, m) if (A[i] == B[j])
		{
			Cnt[j] = 1;
			update(Cnt[j], Sum[r][i][1] - Sum[r][i][j]);
		}
		
		int tsum = 0;
		FORR (j, m, 1) {
			if ((tsum += Cnt[j]) >= modulo)
				tsum -= modulo;
			update(SumV[r], A[i], j, tsum);
		}
	}

	FOR (k, 1, p) 
	{
		r ^= 1;
		memset(SumV[r], 0, sizeof(SumV[r]));
		
		FOR (i, 1, n)
		{
			FOR (j, 1, m)
				Sum[r][i][j] = query(SumV[r], A[i], j);

			memset(Cnt, 0, sizeof(Cnt));
			FOR (j, 1, m) if (A[i] == B[j]) 
			{
				Cnt[j] = 0;

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

			int tsum = 0;
			FORR (j, m, 1) {
				if ((tsum += Cnt[j]) >= modulo)
					tsum -= modulo;
				update(SumV[r], A[i], j, tsum);
			}

			if (k == p)
				FOR (j, 1, m) if (A[i] == B[j])
					if ((ret += Cnt[j]) >= modulo)
						ret -= modulo;
		}
	}

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

	return 0;
}