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

#define maxn 510
#define sigma 510
#define LSB(x) (x&(x-1))^x
#define mod 666013

int n, m, l;
int a[maxn], b[maxn], v[maxn];
int c[maxn][maxn], d[maxn][maxn];
int aib[maxn][maxn];

inline void update(int x, int y, int v)
{
	for (; x<sigma; x += LSB(x)) 
	{
		aib[x][y] += v;
		if (aib[x][y] >= mod) aib[x][y] -= mod;
	}
}

inline int query(int x, int y)
{
	int rez = 0;

	for (; x; x -= LSB(x)) 
	{
		rez += aib[x][y];
		if (rez >= mod) rez -= mod;
	}

	return rez;
}

int main()
{
	freopen("pedefe.in", "r", stdin);
	freopen("pedefe.out", "w", stdout);

	scanf("%d %d %d ", &n, &m, &l);

	int i, j, k, sum;

	for (i=1; i<=n; i++) scanf("%d ", &a[i]);

	for (i=1; i<=m; i++) scanf("%d ", &b[i]);

	for (i=1; i<=l; i++) scanf("%d ", &v[i]);

	a[0] = b[0] = 1;
	c[0][0] = 1;

	for (i=1; i<=l+1; i++)
	{
		memcpy(d, c, sizeof(c));
		memset(c, 0, sizeof(c));
		memset(aib, 0, sizeof(aib));

		for (j=0; j<=n; j++)
		{
			sum = 0;
			for (k=0; k<=m; k++) 
			{
				sum += d[j][k];
				if (sum >= mod) sum -= mod;
				update(a[j], k, sum);

				if (j<n && k<m && a[j+1]==b[k+1] && a[j+1]==v[i])
				{
					c[j+1][k+1] += query(a[j+1], k);
					if (c[j+1][k+1] >= mod) c[j+1][k+1] -= mod;
				}
				else if (j<n && k<m && a[j+1] == b[k+1]) 
					 {
						 d[j+1][k+1] += query(a[j+1], k);
						 if (d[j+1][k+1] >= mod) d[j+1][k+1] -= mod;
					 }
			}
		}
	}

	printf("%d\n", query(sigma, m));

	return 0;
}