#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("pedefe.in");
ofstream g ("pedefe.out");

struct Read {
    ifstream f;
    Read (const string &input) {
        f.open (input);
    }
    int pos = (1 << 30), sz = 0;
    string s;

    int getNextInt() {
        int ret = 0;
        while (s[pos] == ' ') ++pos;
        while (pos < sz && '0' <= s[pos] && s[pos] <= '9') {
            ret *= 10;
            ret += s[pos] - '0';
            ++pos;
        }
        return ret;
    }

    int nextInt() {
        if (pos >= sz) {
            getline (f, s);
            pos = 0;
            sz = s.size();
        }

        return getNextInt();
    }
} in ("pedefe.in");

const int NMAX = 500;
const int MOD = 666013;

int sum[NMAX + 5], bit[NMAX + 5];
int n, m, p;
int a[NMAX + 5], b[NMAX + 5], c[NMAX + 5];
int dp[2][NMAX + 5][NMAX + 5];

inline int lsb (int x) {
    return (x & (-x));
}

void update (int pos, int val) {
    for (pos; pos <= NMAX; pos += lsb (pos)) {
        bit[pos] += val;
        if (bit[pos] >= MOD) bit[pos] -= MOD;
    }
}

int query (int pos) {
    int ret = 0;
    for (pos; pos > 0; pos -= lsb (pos)) {
        ret += bit[pos];
        if (ret >= MOD) ret -= MOD;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL_DEFINE
    freopen (".in", "r", stdin);
#endif
	//n = in.nextInt();
	//m = in.nextInt();
    //p = in.nextInt();
    f >> n >> m >> p;

    for (int i = 1; i <= n; ++i) {
        //a[i] = in.nextInt();
        f >> a[i];
    }
    for (int i = 1; i <= m; ++i) {
        //b[i] = in.nextInt();
        f >> b[i];
    }
    for (int i = 1; i <= p; ++i) {
        //c[i] = in.nextInt();
        f >> c[i];
    }

    for (int k = 0; k <= p; ++k) {
        int kk = (k & 1);
        //memset (sum, 0, sizeof (sum));
        for (int x = 0; x < NMAX + 5; ++x) sum[x] = 0;
        for (int i = 1; i <= n; ++i) {
            //memset (bit, 0, sizeof (bit));
            for (int x = 0; x < NMAX + 5; ++x) bit[x] = 0;
            for (int j = 1; j <= m; ++j) {
                dp[1 - kk][i][j] = 0;
                if (a[i] == b[j]) {
                    int q = query (a[i]) + (k == 0); // sum of dp[kk][ii][jj] so that ii < i, jj < j, a[ii] <= a[i]
                    if (k != p && a[i] == c[k + 1]) {
                        dp[1 - kk][i][j] += q;
                        if (dp[1 - kk][i][j] >= MOD) dp[1 - kk][i][j] -= MOD;
                    } else {
                        dp[kk][i][j] += q;
                        if (dp[kk][i][j] >= MOD) dp[kk][i][j] -= MOD;
                    }
                } else {
                    dp[kk][i][j] = 0;
                }

                update (b[j], sum[j]);
                sum[j] += dp[kk][i][j];
                if (sum[j] >= MOD) sum[j] -= MOD;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            ans += dp[(p & 1)][i][j];
            if (ans >= MOD) ans -= MOD;
        }
    }

    g << ans << '\n';

    in.f.close();
    g.close();
    return 0;
}