#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

const int MAX = 510;
const int MOD = 666013;
int N, M, K;
int S1[MAX];
int S2[MAX];
int S3[MAX];
int D[2][MAX][MAX];
int s[2][MAX][MAX];

void Read();
void Dyn();

int main()
{
    Read();
    Dyn();

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i;

    fin >> N >> M >> K;
    for ( i = 1; i <= N; i++ )
        fin >> S1[i];
    for ( i = 1; i <= M; i++ )
        fin >> S2[i];
    for ( i = 1; i <= K; i++ )
        fin >> S3[i];
}

void Dyn()
{
    int i, j, k, q, t, p;
    int rez = 0;
    bool lc, lp;

    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
            if ( S1[i] == S2[j] )
            {
                D[0][i][j]++;
                if ( S1[i] == S3[1] )
                    D[1][i][j]++;
            }

    for ( k = 1, lc = 1, lp = 0; k <= K; k++, lc = !lc, lp = !lp )
        for ( i = 1; i <= N; i++ )
            for ( j = 1; j <= M; j++ )
            {
                if ( S1[i] == S2[j] )
                {
                    if ( k > 1 )
                        D[lc][i][j] = 0;

                    for ( q = 1; q < i; q++ )
                        if ( S1[q] <= S1[i] )
                        {
                            D[lc][i][j] = ( D[lc][i][j] + s[lc][q][j - 1] ) % MOD;
                            if ( S1[i] == S3[k] )
                                D[lc][i][j] = ( D[lc][i][j] + s[lp][q][j - 1] ) % MOD;
                        }

                  //  cout << k << ' ' << D[k][i][j]; cin.get();
                }

                s[lc][i][j] = ( s[lc][i][j - 1] + D[lc][i][j] ) % MOD;
                if ( k == K )
                    rez = ( rez + D[lc][i][j] ) % MOD;
            }

    fout << rez << '\n';
}