#include <bits/stdc++.h>

using namespace std;

ifstream fin("pedefe.in");
ofstream fout("pedefe.out");

const int NMAX = 502;
const int MOD = 666013;

int s1[NMAX],s2[NMAX],s3[105];
int aib[NMAX],dp[2][NMAX][NMAX],smp[NMAX];
int n,m,p;

int q(int x)
{
    return (x&(-x));
}

void update(int poz,int val)
{
    for(int i=poz+1;i<=501;i+=q(i))
        aib[i]=(aib[i]+val)%MOD;
}

int query(int poz)
{
    int rasp=0;
    for(int i=poz+1;i>=1;i-=q(i))
        rasp=(rasp+aib[i])%MOD;
    return rasp;
}

int main()
{
    fin >> n >> m >> p;
    for(int i=1;i<=n;i++) fin >> s1[i];
    for(int i=1;i<=m;i++) fin >> s2[i];
    for(int i=1;i<=p;i++) fin >> s3[i];
    dp[0][0][0]=1;
    int ok=1;
    for(int k=0;k<=p;k++)
    {
        ok=1-ok;
        for(int i=1;i<=NMAX;i++) smp[i]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=NMAX;j++) aib[j]=0;
            if(k==0) update(0, 1);
            for(int j=1;j<=m;j++)
            {
                dp[1-ok][i][j]=0;
                if(k<p and s1[i]==s2[j])
                {
                    if(s1[i]==s3[k+1]) dp[1-ok][i][j] += query(s2[j]);
                    else               dp[ok][i][j]   += query(s2[j]);
                }
                else dp[k][i][j]=0;
                update(s2[j],smp[j]);
                smp[j]=(smp[j]+dp[k][i][j])%MOD;
            }
        }
    }
    int rasp=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            rasp+=dp[p%2][i][j];
            rasp%=MOD;
        }
    }
    fout << rasp;
    return 0;
}