#include <bits/stdc++.h>
#define zeros(x) ( (x ^ (x - 1)) & x )
#define maxN 502
#define maxP 102
#define mod 666013
using namespace std;
int n, m, p, sol, s1[maxN], s2[maxN], s3[maxP], s[maxN];
int fp1[maxN], fp2[maxN], aib[maxN], dp[2][maxN][maxN];
void update(int x, int y)
{
    int i;
    for (i = x + 1; i < maxN; i += zeros(i))
    {
        aib[i] += y;
        if (aib[i] > mod)
            aib[i] -= mod;
    }
}
int sum(int x)
{
    int i, s = 0;
    for (i = x + 1; i > 0; i -= zeros(i))
    {
        s += aib[i];
        if (s > mod)
            s -= mod;
    }
    return s;
}
void read()
{
    int i;
    freopen("pedefe.in", "r", stdin);
    scanf("%d %d %d", &n, &m, &p);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d", &s1[i]);
        if (!fp1[s1[i]])
            fp1[s1[i]] = i;
    }
    for (i = 1; i <= m; ++ i)
    {
        scanf("%d", &s2[i]);
        if (!fp2[s2[i]])
            fp2[s2[i]] = i;
    }
    for (i = 1; i <= p; ++ i)
        scanf("%d", &s3[i]);
}
void solve()
{
    int i, j, k, act = 0;
    dp[0][0][0] = 1;
    for (i = 0; i <= p; ++ i)
    {
        memset(s, 0, sizeof(s));
        for (j = 1; j <= n; ++ j)
        {
            memset(aib, 0, sizeof(aib));
            if (i == 0)
                update(0, 1);
            for (k = 1; k <= m; ++ k)
            {
                dp[!act][j][k] = 0;
                if (s1[j] == s2[k])
                {
                    if (s1[j] == s3[i + 1] && i < p)
                        dp[!act][j][k] += sum(s1[j]);
                    else
                        dp[act][j][k] += sum(s1[j]);
                }
                else
                    dp[act][j][k] = 0;

                update(s2[k], s[k]);
                s[k] += dp[act][j][k];
                if (s[k] >= mod)
                    s[k] -= mod;
                if (i == p)
                {
                    sol += dp[act][j][k];
                    if (sol >= mod)
                        sol -= mod;
                }
            }
        }
        act = !act;
    }
}
void write()
{
    freopen("pedefe.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
}