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

#define MAXN 501
#define MAXC 501
#define MAXP 101
#define MOD 666013

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

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

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])
	
	nr[0][0][0] = 1;
	
	int step = 1;
	for (int k = 1; k <= P; k++, step ^= 1)
	{
		nr[step][0][0] = 0;
		memset( S, 0, sizeof( S ) );
		if (nr[1 ^ step][0][0])
			S[1 ^ step][0] = 1;

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

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

					if (a[i] == c[k])
					{
						nr[step][i][j] += S[1 ^ step][y];
						if (nr[step][i][j] >= MOD)
							nr[step][i][j] -= MOD;
					}
					else
					{
						nr[step][i][j] += S[step][y];
						if (nr[step][i][j] >= MOD)
							nr[step][i][j] -= MOD;
					}
				}
			}

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

				S[step][j] += nr[step][i][j];
				if (S[step][j] >= MOD)
					S[step][j] -= MOD;
				S[1 ^ step][j] += nr[1 ^ step][i][j];
				if (S[1 ^ step][j] >= MOD)
					S[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;
}