#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MOD = 666013;

int add(int a, int b)
{
        a += b;
        if (a >= MOD)
                a -= MOD;
        if (a < 0)
                a += MOD;
        return a;
}

int mul(int a, int b)
{
        return a * (ll) b % MOD;
}


const int N = 500 + 7;

int n, m, p, a[N], b[N], c[N];
int fen[N][N], nn, mm, dp[N][N], ndp[N][N];
vector <pair <int, int>> u[N];
int ua[N][N], ub[N][N];

void add(int x, int y, int a)
{
        x += 3;
        y += 3;
        for (int i = x; i <= nn; i += i & (-i))
                for (int j = y; j <= mm; j += j & (-j))
                        fen[i][j] = add(fen[i][j], a);
}

int get(int x, int y)
{
        x += 3;
        y += 3;
        int r = 0;
        for (int i = x; i; i -= i & (-i))
                for (int j = y; j; j -= j & (-j))
                        r = add(r, fen[i][j]);
        return r;
}

void clr()
{
        for (int i = 1; i <= nn; i++)
                for (int j = 1; j <= mm; j++)
                        fen[i][j] = 0;
}

int main()
{
        freopen ("pedefe.in", "r", stdin);
        freopen ("pedefe.out", "w", stdout);

        cin >> n >> m >> p;
        nn = n + 6;
        mm = m + 6;

        for (int i = 1; i <= n; i++)
                cin >> a[i];
        for (int i = 1; i <= m; i++)
                cin >> b[i];
        for (int i = 1; i <= p; i++)
                cin >> c[i];

        for (int x = 0; x < N; x++)
        {
                ua[n + 1][x] = n + 1;
                ub[m + 1][x] = m + 1;
        }
        for (int i = n; i >= 1; i--)
        {
                for (int x = 1; x < N; x++)
                        ua[i][x] = ua[i + 1][x];
                ua[i][a[i]] = i;
        }

        for (int i = m; i >= 1; i--)
        {
                for (int x = 0; x < N; x++)
                        ub[i][x] = ub[i + 1][x];
                ub[i][b[i]] = i;
        }

        dp[0][0] = 1;
        c[p + 1] = N - 1;

        for (int i = 1; i < p; i++)
                if (c[i] > c[i + 1])
                {
                        cout << "0\n";
                        return 0;
                } /// useless

        for (int i = 0; i <= n; i++)
                for (int j = 0; j <= m; j++)
                        if (a[i] == b[j])
                                u[a[i]].push_back({i, j});

        for (int it = 1; it <= p + 1; it++)
        {
                clr();
                for (int x = c[it - 1]; x < c[it]; x++)
                        for (auto &it : u[x])
                        {
                                int i = it.first, j = it.second;
                                dp[i][j] = add(dp[i][j], get(i - 1, j - 1));
                                add(i, j, dp[i][j]);
                        }
                if (it <= p)
                {
                        int val = c[it];
                        for (int x = c[it - 1]; x <= c[it]; x++)
                                for (auto &it : u[x])
                                {
                                        int i = it.first, j = it.second;
                                        int ni = ua[i + 1][val], nj = ub[j + 1][val];
                                        if (ni <= n && nj <= m)
                                                ndp[ni][nj] = add(ndp[ni][nj], dp[i][j]);
                                }
                        for (int i = 0; i <= n; i++)
                                for (int j = 0; j <= m; j++)
                                {
                                        dp[i][j] = ndp[i][j];
                                        ndp[i][j] = 0;
                                }
                }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                        ans = add(ans, dp[i][j]);
        cout << ans << "\n";

}