#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int nmax=505;
const int sigma=500;
const int mod=666013;
int aib[2][nmax];
int dp[2][nmax][nmax],sum[2][nmax][nmax];
int S1[nmax],S2[nmax],S3[nmax];
int n,m,p,i,j,k,wh,use,ans;
void md(int &a)
{
    if(a>=mod)
        a-=mod;
}
inline int lbit(int x)
{
    return (((x^(x-1))&x));
}
void update(int wh,int poz,int val)
{
    for(int idx=poz;idx<=sigma;idx+=lbit(idx))
        {
            aib[wh][idx]+=val;
            md(aib[wh][idx]);
        }
}
int compute(int wh,int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
    {
         ret+=aib[wh][idx];
         md(ret);
    }
    return ret;
}
int main()
{
    ifstream f("pedefe.in");
    ofstream g("pedefe.out");
    f>>n>>m>>p;
    for(i=1;i<=n;i++)
        f>>S1[i];
    for(i=1;i<=m;i++)
        f>>S2[i];
    for(i=1;i<=p;i++)
        f>>S3[i];
    S3[0]=-1;
    for(i=0;i<=p;i++)
    {
        use=1-use;
        for(j=1;j<=n;j++)
        {
            if(i==0)
            {
               update(use,1,1);
            }
            if(i==1)
            {
                update(1-use,1,1);
            }
            for(k=1;k<=m;k++)
            {
                if(S1[j]==S2[k])
               {
                  dp[use][j][k]=compute((use^(S1[j]==S3[i])),S1[j]);
               }else dp[use][j][k]=0;
               update(1-use,S2[k],sum[1-use][j-1][k]);
               update(use,S2[k],sum[use][j-1][k]);
               sum[1-use][j][k]=sum[1-use][j-1][k]+dp[1-use][j][k];
               md(sum[1-use][j][k]);
               sum[use][j][k]=sum[use][j-1][k]+dp[use][j][k];
               md(sum[use][j][k]);
            }
            memset(aib[0],0,sizeof(aib[0]));
            memset(aib[1],0,sizeof(aib[1]));
        }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        ans+=dp[use][i][j];
        md(ans);
    }
    g<<ans;
    return 0;
}