#include<fstream>

using namespace std;

const char iname[]="pedefe.in";
const char oname[]="pedefe.out";
const int maxn=505;
const int mod=666013;

ifstream f(iname);
ofstream g(oname);

int n,m,p,a[maxn],b[maxn],c[maxn],i,j,k,aibp[maxn][maxn],aibn[maxn][maxn],sn,sp,dp[2][maxn][maxn];

int query(int *aib,int x)
{
    if(x==0)
        return aib[0];
    int s=0;
    for(;x;x-=x&-x)
    {
        s+=aib[x];
        if(s>=mod)
            s-=mod;
    }
    return s;
}

void update(int *aib,int x,int v)
{
    if(x==0)
        ++x,aib[0]+=v;
    for(;x<maxn;x+=x&-x)
    {
        aib[x]+=v;
        if(aib[x]>=mod)
            aib[x]-=mod;
    }
}

int main()
{
    f>>n>>m>>p;
    for(i=1;i<=n;++i)
        f>>a[i];
    for(j=1;j<=m;++j)
        f>>b[j];
    for(k=1;k<=p;++k)
        f>>c[k];
    for(k=0;k<=p;++k)
    {
        memset(aibp,0,sizeof(aibp));
        memset(aibn,0,sizeof(aibn));
        memset(dp[k&1],0,sizeof(dp[k&1]));
        for(i=0;i<=n;++i)
        {
            sn=sp=0;
            for(j=0;j<=m;++j)
                if(a[i]==b[j])
                    if(a[i]==c[max(k,1)])
                        dp[k&1][i][j]=query(aibp[j-1],a[i]);
                    else
                        dp[k&1][i][j]=query(aibn[j-1],a[i]);
            for(j=0;j<=m;++j)
            {
                if(k==0&&i==0&&j==0)
                    dp[k&1][i][j]=1;
                sn+=dp[k&1][i][j];
                if(sn>=mod)
                    sn-=mod;
                sp+=dp[k-1&1][i][j];
                if(sp>=mod)
                    sp-=mod;
                update(aibp[j],a[i],sp);
                update(aibn[j],a[i],sn);
            }
        }
    }
    g<<query(aibn[m],maxn-1)<<"\n";
}