#include<fstream>
#include<memory.h>

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,aib[maxn][maxn],s,past[maxn][maxn],future[maxn][maxn];

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

inline void update(int *aib,int x,int 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];
    future[0][0]=1;
    a[0]=b[0]=1;
    for(k=0;k<=p;++k)
    {
        memset(aib,0,sizeof(aib));
        memcpy(past,future,sizeof(future));
        memset(future,0,sizeof(future));
        for(i=0;i<=n;++i)
        {
            s=0;
            for(j=0;j<=m;++j)
            {
                s+=past[i][j];
                if(s>=mod)
                    s-=mod;
                update(aib[j],a[i],s);
                if(i<n&&j<m&&a[i+1]==b[j+1])
                {
                    if(a[i+1]==c[k+1])
                    {
                        future[i+1][j+1]+=query(aib[j],a[i+1]);
                        if(future[i+1][j+1]>=mod)
                            future[i+1][j+1]-=mod;
                    }
                    else
                    {
                        past[i+1][j+1]+=query(aib[j],a[i+1]);
                        if(past[i+1][j+1]>=mod)
                            past[i+1][j+1]-=mod;
                    }
                }
            }
        }
    }
    g<<query(aib[m],maxn-1)<<"\n";
}