#include <fstream>
#include <cstring>
#define DIM 510
#define MOD 666013
using namespace std;

ifstream fin ("pedefe.in");
ofstream fout ("pedefe.out");
int maxi = 500;
int d[2][DIM][DIM],s[DIM],aib[DIM],a[DIM],b[DIM],c[DIM];
int n,m,p,i,j,k,t,ok;
inline void update (int poz, int val){
    for (;poz<=maxi;poz+=(poz&-poz))
        aib[poz] = (aib[poz] + val)%MOD;
}
inline int query (int poz){
    int sol = 0;
    for (;poz;poz-=(poz&-poz))
        sol = (sol+aib[poz])%MOD;
    return sol;
}
int main (){

    fin>>n>>m>>p;
    for (i=1;i<=n;i++)
        fin>>a[i];
    for (i=1;i<=m;i++)
        fin>>b[i];
    for (i=1;i<=p;i++)
        fin>>c[i];

    /// d[i][j][k] - nr de siruri crescatoare care se pot forma folosind primele i caractere din primul
    /// j din al doilea si primele k sa fie subsir, a[i] = b[j]
    d[0][0][0] = 1;
    t = ok = 1;
    for (k=0;k<=p;k++){
        memset (s,0,sizeof s);
        memset (d[1-t],0,sizeof d[1-t]);
        for (i=1;i<=n;i++){
            memset (aib,0,sizeof aib);
            for (j=1;j<=m;j++){
                if (a[i] == b[j]){
                    if (a[i] == c[k+1])
                        d[1-t][i][j] += query (a[i])+ok;
                    else d[t][i][j] += query (a[i])+ok;
                }
                update (b[j],s[j]);
                s[j] += d[t][i][j];
            }}
        t = 1-t;
        if (ok) ok = 0;
    }

    int sol = 0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            sol = (sol+d[1-t][i][j])%MOD;
    fout<<sol;

    return 0;
}