#include<stdio.h>
#include<string.h>
#define Mod 666013
#define Nm 501
#define max(a,b) ((a)>(b)?(a):(b))
int A[Nm][Nm],S1[Nm],S2[Nm],S3[Nm],n,m,q,vm;

void read()
{
    int i;

    freopen("pedefe.in","r",stdin);
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<=n;++i)
    {
        scanf("%d",S1+i);
        vm=max(vm,S1[i]);
    }
    for(i=1;i<=m;++i)
    {
        scanf("%d",S2+i);
        vm=max(vm,S2[i]);
    }
    for(i=1;i<=q;++i)
    {
        scanf("%d",S3+i);
        vm=max(vm,S3[i]);
    }
}

void update(int i, int j, int v)
{
    int k;
    
    for(;i<=m;i+=i&(i-1)^i)
        for(k=j;k<=vm;k+=k&(k-1)^k)
        {
            A[i][k]+=v;
            if(A[i][k]>=Mod)
                A[i][k]-=Mod;
        }
}

int query(int i, int j)
{
    int k,ans=0;

    for(;i;i-=i&(i-1)^i)
        for(k=j;k;k-=k&(k-1)^k)
        {
            ans+=A[i][k];
            if(ans>=Mod)
                ans-=Mod;
        }
    return ans;
}

int solve()
{
    int M[2][Nm][Nm],V[Nm],i,j,k,l,c,p,ans=0;

    M[0][0][0]=1;
    for(i=1;i<=n;++i)
        M[0][i][0]=1;
    for(j=1;j<=m;++j)
        M[0][0][j]=1;

    S3[q+1]=Nm; c=0; p=1;
    for(k=0;k<=q;++k)
    {
        for(j=0;j<=m;++j)
            memset(A[j],0,sizeof(A[j]));
        for(i=1;i<=n;++i)
        {
            for(j=1;j<=m;++j)
            {
                V[j]=0;
                if(S1[i]==S2[j] && S1[i]>=S3[k] && S1[i]<=S3[k+1])
                {
                    V[j]+=query(j-1,S1[i]);
                    if(!k)
                        ++V[j];
                    if(S1[i]==S3[k])
                    {
                        V[j]+=M[p][i-1][j-1];
                        if(k==q)
                        {
                            ans+=M[p][i-1][j-1];
                            if(ans>=Mod)
                                ans-=Mod;
                        }
                    }
                    if(V[j]>=Mod)
                        V[j]-=Mod;
                }
                M[c][i][j]=V[j]+M[c][i-1][j]+M[c][i][j-1]-M[c][i-1][j-1];
                while(M[c][i][j]>=Mod)
                    M[c][i][j]-=Mod;
            }
            for(j=1;j<=m;++j)
                if(V[j])
                    update(j,S1[i],V[j]);
        }
        c^=1; p^=1;
    }

    return ans;
}

void write(int ans)
{
    freopen("pedefe.out","w",stdout);
    printf("%d\n",ans);
}

int main()
{
    read();
    write(solve());
    return 0;
}