#include <stdio.h>
#include <string>

#define maxn 510
#define sigma 510
#define LSB(x) (x&(x-1))^x
#define mod 666013

int n, m, l;
int a[maxn], b[maxn], v[maxn];
int c[maxn][maxn], d[maxn][maxn];
int aib[maxn][maxn];

inline void update(int x, int y, int v)
{
    for (; x<sigma; x += LSB(x))
    {
        aib[x][y] += v;
        if (aib[x][y] >= mod) aib[x][y] -= mod;
    }
}

inline int query(int x, int y)
{
    int rez = 0;

    for (; x; x -= LSB(x))
    {
        rez += aib[x][y];
        if (rez >= mod) rez -= mod;
    }

    return rez;
}

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

    scanf("%d %d %d ", &n, &m, &l);

    int i, j, k, sum;

    for (i=1; i<=n; i++) scanf("%d ", &a[i]);

    for (i=1; i<=m; i++) scanf("%d ", &b[i]);

    for (i=1; i<=l; i++) scanf("%d ", &v[i]);

    a[0] = b[0] = 1;
    c[0][0] = 1;

    for (i=1; i<=l+1; i++)
    {
        memcpy(d, c, sizeof(c));
        memset(c, 0, sizeof(c));
        memset(aib, 0, sizeof(aib));

        for (j=0; j<=n; j++)
        {
            sum = 0;
            for (k=0; k<=m; k++)
            {
                sum += d[j][k];
                if (sum >= mod) sum -= mod;
                update(a[j], k, sum);

                if (j<n && k<m && a[j+1]==b[k+1] && a[j+1]==v[i])
                {
                    c[j+1][k+1] += query(a[j+1], k);
                    if (c[j+1][k+1] >= mod) c[j+1][k+1] -= mod;
                }
                else if (j<n && k<m && a[j+1] == b[k+1])
                     {
                         d[j+1][k+1] += query(a[j+1], k);
                         if (d[j+1][k+1] >= mod) d[j+1][k+1] -= mod;
                     }
            }
        }
    }

    printf("%d\n", query(sigma, m));

    return 0;
}