#include <stdio.h>
#include <string.h>

#define MAXN 502
#define MAXC 502
#define MAXP 102
#define MOD 666013

int N, M, P;
int a[MAXN], b[MAXN], c[MAXP];
int nr[2][MAXN][MAXN];
int S[2][MAXC], Sc[2][MAXN];

//numarul de subsiruri crescatoare comune pentru 2 siruri
//avand un al treilea ca subsir

inline void add( int step, int poz, int val )
{
	for (poz++; poz < MAXN; poz += (poz ^ (poz - 1)) & poz)
	{
		S[step][poz] += val;
		if (S[step][poz] >= MOD)
			S[step][poz] -= MOD;
	}
}

inline int query( int step, int poz )
{
	int rez = 0;
	for (poz++; poz; poz -= (poz ^ (poz - 1)) & poz)
	{
		rez += S[step][poz];
		if (rez >= MOD)
			rez -= MOD;
	}
	return rez;
}


int main()
{
	freopen("pedefe.in", "rt", stdin);
	freopen("pedefe.out", "wt", stdout);
	
	scanf("%d %d %d", &N, &M, &P);
	a[0] = b[0] = c[0] = 0;		//numerele sunt in intervalul [1...500]
	for (int i = 1; i <= N; i++)
		scanf("%d", a + i);
	for (int j = 1; j <= M; j++)
		scanf("%d", b + j);
	for (int k = 1; k <= P; k++)
		scanf("%d", c + k);

	//nr[k][i][j] = nr de subsiruri care contin primele k valori din c, si se termina la pozitiile i in sirul a si j in sirul b (a[i] == b[j])
	
	int step = 0;
	for (int k = 0; k <= P; k++, step ^= 1)
	{
		nr[step][0][0] = (k == 0);
		memset( Sc, 0, sizeof( Sc ) );
		Sc[ step ][0] = nr[step][0][0];
		Sc[ 1 ^ step ][0] = nr[1 ^ step][0][0];

		for (int i = 1; i <= N; i++)
		{
			memset(S, 0, sizeof(S));
			for (int j = 1; j <= M; j++)
			{
				nr[step][i][j] = 0;
				add( step, b[j - 1], Sc[step][j - 1] );
				add( 1 ^ step, b[j - 1], Sc[1 ^ step][j - 1] );

				if (a[i] != b[j])
					continue;

				if (a[i] == c[k])
					nr[step][i][j] = query( 1 ^ step, a[i] );
				else
					nr[step][i][j] = query( step, a[i] );
			}

			for (int j = 0; j <= M; j++)
			{
				if (a[i] != b[j])
					continue;

				Sc[step][j] += nr[step][i][j];
				if (Sc[step][j] >= MOD)
					Sc[step][j] -= MOD;
				Sc[1 ^ step][j] += nr[1 ^ step][i][j];
				if (Sc[1 ^ step][j] >= MOD)
					Sc[1 ^ step][j] -= MOD;
			}
		}
	}

	int S = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (a[i] == b[j])
			{
				S += nr[1 ^ step][i][j];
				if (S >= MOD)
					S -= MOD;
			}
	printf("%d\n", S);
	return 0;
}