/**
  *  Worg
  */
#include <cstdio>
#include <cstring>
#include <algorithm>

#define lsb(x) (x & (-x))

FILE *fin = freopen("pedefe.in", "r", stdin);
FILE *fout = freopen("pedefe.out", "w", stdout);

const int kMaxN = 500 + 1;
const int kMaxValue = 500 + 1;
const int kModulo = 666013;

/*-------- Input data --------*/
int N, M, P;
int A[kMaxN], B[kMaxN], C[kMaxN];
/*-------- Algorithm data --------*/
int bit[kMaxValue];

int dp[2][kMaxN][kMaxN];
int count[kMaxN];
/*-------- --------*/

void ReadInput() {
    scanf("%d%d%d", &N, &M, &P);
    for(int i = 1; i <= N; i++) {
        scanf("%d", &A[i]);
    }
    for(int i = 1; i <= M; i++) {
        scanf("%d", &B[i]);
    }
    for(int i = 1; i <= P; i++) {
        scanf("%d", &C[i]);
    }
}


void Add(int& to, int from) {
    to = (to + from >= kModulo) ? (to + from - kModulo) : (to + from);
}

void Update(int position, int value) {
    for(int i = position; i < kMaxValue; i += lsb(i)) {
        Add(bit[i], value);
    }
}

int Query(int position) {
    int answer = 0;
    for(int i = position; i > 0; i -= lsb(i)) {
        Add(answer, bit[i]);
    }
    return answer;
}

int RunDP() {
    dp[0][0][0] = 1;
    int old = 0, now = 1;
    for(int k = 0; k <= P; k++) {
        memset(count, 0, sizeof(count));
        for(int i = 1; i <= N; i++) {
            memset(bit, 0, sizeof(bit));  //  Reset bit
            for(int j = 1; j <= M; j++) {
                dp[now][i][j] = 0;  //  Reset value
                if(A[i] == B[j]) {
                    int x = Query(A[i]);
                    if(k == 0) {
                        Add(x, 1);
                    }

                    if(k < P && A[i] == C[k + 1]) {
                        Add(dp[now][i][j], x);
                    } else {
                        Add(dp[old][i][j], x);
                    }
                } else {
                    dp[old][i][j] = 0;
                }
                Update(B[j], count[j]);
                Add(count[j], dp[old][i][j]);
            }
        }
        std::swap(now, old);
    }

    int answer = 0;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            Add(answer, dp[now][i][j]);
        }
    }
    return answer;
}

int main() {
    ReadInput();
    printf("%d\n", RunDP());
    return 0;
}