#include<cstdio>
#include<cstring>
int a[505],b[505],c[505],aib[505],cnt[505];
int d[2][512][512];
void add(int &a,int b)
{
a+=b;
while(a>=666013)
a-=666013;
}
void update(int poz,int val)
{
for(++poz;poz<512;poz+=poz&-poz)
add(aib[poz],val);
}
int query(int poz)
{
int sum=0;
for(++poz;poz>0;poz-=poz&-poz)
add(sum,aib[poz]);
return sum;
}
int main()
{
freopen("pedefe.in","r",stdin);
freopen("pedefe.out","w",stdout);
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=p;i++)
scanf("%d",&c[i]);
d[0][0][0]=1;
for(int i=0;i<=p;i++)
{
memset(cnt,0,sizeof(cnt));
int num=i%2;
for(int j=1;j<=n;j++)
{
memset(aib,0,sizeof(aib));
if (i==0)
update(0,1);
for(int e=1;e<=m;e++)
{
d[1-num][j][e]=0;
if (a[j]==b[e])
{
int before=query(a[j]);
if (i<p && c[i+1]==a[j])
add(d[1-num][j][e],before);
else
add(d[num][j][e],before);
}
else
d[num][j][e]=0;
update(b[e],cnt[e]);
add(cnt[e],d[num][j][e]);
}
}
}
int sol=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
add(sol,d[p&1][i][j]);
printf("%d\n",sol);
return 0;
}