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

using namespace std;

typedef long long ll;

const int MOD = 666013;

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

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

const int N = 500 + 7;
const int P = 100 + 7;
int n, m, p, dp[N][N], a[N], b[N], c[P], ua[N][N], ub[N][N], ndp[N][N];
vector <pair <int, int>> eq[N];

int aib[N][N];

void add(int x, int y, int val)
{
        x++;
        y++;
        if (x == 0 || y == 0)
                return;
        for (int i = x; i <= n + 1; i += i & (-i))
                for (int j = y; j <= m + 1; j += j & (-j))
                        aib[i][j] = add(aib[i][j], val);
}

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

void clr()
{
        for (int i = 1; i <= n + 1; i++)
        {
                for (int j = 1; j <= m + 1; j++)
                {
                        aib[i][j] = 0;
                }
        }
}

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

        cin >> n >> m >> p;
        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 = 1; x < N; x++)
        {
                ua[n + 1][x] = n + 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 x = 1; x < N; x++)
        {
                ub[m + 1][x] = m + 1;
        }
        for (int i = m; i >= 1; i--)
        {
                for (int x = 1; x < N; x++)
                {
                        ub[i][x] = ub[i + 1][x];
                }
                ub[i][b[i]] = i;
        }

        a[0] = b[0] = -1;
        dp[0][0] = 1;
        c[p + 1] = -2;

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

        for (int it = 1; it <= p + 1; it++)
        {
                add(0, 0, dp[0][0]);
                for (int x = 1; x < N; x++)
                        if (x != c[it])
                                for (auto &itr : eq[x])
                                {
                                        int i = itr.first, j = itr.second;
                                        dp[i][j] = add(dp[i][j], get(i - 1, j - 1));
                                        add(i, j, dp[i][j]);
                                }
                clr();
                if (it <= p)
                {
                        for (int i = 0; i <= n; i++)
                                for (int j = 0; j <= m; j++)
                                        if (dp[i][j] && a[i] < c[it])
                                        {
                                                int ni = ua[i + 1][c[it]], nj = ub[j + 1][c[it]];
                                                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";


        return 0;
}