#include <stdio.h>
#include <string.h>
 
#define MAXN 502
#define MAXC 502
#define MAXP 102
#define MOD 666013
 
int N, M, P;
int a[MAXN], b[MAXN], c[MAXP];
int nr[2][MAXN][MAXN];
int S[2][MAXC], Sc[2][MAXN];
 
//numarul de subsiruri crescatoare comune pentru 2 siruri
//avand un al treilea ca subsir
 
inline void add( int step, int poz, int val )
{
    for (poz++; poz < MAXN; poz += (poz ^ (poz - 1)) & poz)
    {
        S[step][poz] += val;
        if (S[step][poz] >= MOD)
            S[step][poz] -= MOD;
    }
}
 
inline int query( int step, int poz )
{
    int rez = 0;
    for (poz++; poz; poz -= (poz ^ (poz - 1)) & poz)
    {
        rez += S[step][poz];
        if (rez >= MOD)
            rez -= MOD;
    }
    return rez;
}
 
 
int main()
{
    freopen("pedefe.in", "rt", stdin);
    freopen("pedefe.out", "wt", stdout);
     
    scanf("%d %d %d", &N, &M, &P);
    a[0] = b[0] = c[0] = 0;     //numerele sunt in intervalul [1...500]
    for (int i = 1; i <= N; i++)
        scanf("%d", a + i);
    for (int j = 1; j <= M; j++)
        scanf("%d", b + j);
    for (int k = 1; k <= P; k++)
        scanf("%d", c + k);
 
    //nr[k][i][j] = nr de subsiruri care contin primele k valori din c, si se termina la pozitiile i in sirul a si j in sirul b (a[i] == b[j])
     
    int step = 0;
    for (int k = 0; k <= P; k++, step ^= 1)
    {
        nr[step][0][0] = (k == 0);
        memset( Sc, 0, sizeof( Sc ) );
        Sc[ step ][0] = nr[step][0][0];
        Sc[ 1 ^ step ][0] = nr[1 ^ step][0][0];
 
        for (int i = 1; i <= N; i++)
        {
            memset(S, 0, sizeof(S));
            for (int j = 1; j <= M; j++)
            {
                nr[step][i][j] = 0;
                add( step, b[j - 1], Sc[step][j - 1] );
                add( 1 ^ step, b[j - 1], Sc[1 ^ step][j - 1] );
 
                if (a[i] != b[j])
                    continue;
 
                if (a[i] == c[k])
                    nr[step][i][j] = query( 1 ^ step, a[i] );
                else
                    nr[step][i][j] = query( step, a[i] );
            }
 
            for (int j = 0; j <= M; j++)
            {
                if (a[i] != b[j])
                    continue;
 
                Sc[step][j] += nr[step][i][j];
                if (Sc[step][j] >= MOD)
                    Sc[step][j] -= MOD;
                Sc[1 ^ step][j] += nr[1 ^ step][i][j];
                if (Sc[1 ^ step][j] >= MOD)
                    Sc[1 ^ step][j] -= MOD;
            }
        }
    }
 
    int S = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            if (a[i] == b[j])
            {
                S += nr[1 ^ step][i][j];
                if (S >= MOD)
                    S -= MOD;
            }
    printf("%d\n", S);
    return 0;
}