# include <cstdio>
# include <cstring>

const char *FIN = "pedefe.in", *FOU = "pedefe.out";
const int MAX = 502, MOD = 666013;

int N, M, L, S[3][MAX], aib[MAX][MAX], dp[2][MAX][MAX];

inline void mod (int &a) {
    if (a >= MOD) a -= MOD;
}

inline void update (int a, int b, int val) {
    for (; a < MAX; a += a & -a)
        mod (aib[a][b] += val);
}

inline int query (int a, int b) {
    int sol;
    for (sol = 0; a; a -= a & -a)
        mod (sol += aib[a][b]);
    return sol;
}

inline void cit (int *A, int N) {
    A[0] = 1;
    for (int i = 1; i <= N; ++i)
        scanf ("%d", A + i);
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d %d", &N, &M, &L);
    cit (S[0], N), cit (S[1], M), cit (S[2], L);

    dp[0][0][0] = 1;
    for (int i = 1, K = 1; i <= L + 1; ++i, K ^= 1) {
        memset (dp[K], 0, sizeof (dp[K]));
        memset (aib, 0, sizeof (aib));

        for (int j = 0; j <= N; ++j)
            for (int k = 0, suma = 0; k <= M; ++k) {
                mod (suma += dp[K ^ 1][j][k]);
                update (S[0][j], k, suma);
                if (j < N && k < M && S[0][j + 1] == S[1][k + 1])
                    mod (dp[K ^ (S[1][k + 1] == S[2][i] ? 0 : 1)][j + 1][k + 1] += query (S[0][j + 1], k));
            }
    }
    fprintf (fopen (FOU, "w"), "%d", query (MAX, M));
}