#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;
 
void update(int poz,int val)
{
    for(int i=poz+1;i<=501;i+=(i&(-i)))
        aib[i]=(aib[i]+val)%MOD;
}
 
int query(int poz)
{
    int rasp=0;
    for(int i=poz+1;i>=1;i-=(i&(-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;
        memset(smp,0,sizeof(smp));
        for(int i=1;i<=n;i++)
        {
            memset(aib,0,sizeof(aib));
            if(k==0) update(0,1);
            for(int j=1;j<=m;j++)
            {
                dp[1-ok][i][j]=0;
                if(s1[i]==s2[j])
                {
                    if(k<p and s1[i]==s3[k+1]) dp[1-ok][i][j] += query(s2[j]);
                    else              	       dp[ok][i][j]   += query(s2[j]);
                }
                else dp[ok][i][j]=0;
                update(s2[j],smp[j]);
                smp[j]=(smp[j]+dp[ok][i][j])%MOD;
            }
        }
    }
    int rasp=0;
    int P=p%2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            rasp=(rasp+dp[P][i][j])%MOD;
 
    fout << rasp;
    return 0;
}