#include <fstream>
#include <vector>
using namespace std;
ifstream f("pedefe.in");
ofstream g("pedefe.out");
int N, M, p;
const int NMax = 505;
const int PMax = 105;
int S1[NMax], S2[NMax], S3[NMax];
int DP[2][NMax][NMax];
int S[2][NMax][NMax];
int Arb[2][NMax];
int res = 0;
int Partial[2][NMax][NMax];
vector <int> V;
int Use[NMax], Use2[NMax], Max;
const int MOD = 666013;
int P[505];
void Read()
{
    f >> N >> M >> p;
    for(int i = 1; i <= N; i++)
        f >> S1[i], Use[S1[i]] = 1;
    for(int i = 1; i <= M; i++)
        f >> S2[i], Use2[S2[i]] = 1;
    for(int i = 1; i <= p; i++)
        f >> S3[i];
    V.push_back(0);
    P[0] = 1;
    Max = 1;
    for(int i = 1; i <= 500; i++)
    {
        if(Use[i] == 1 && Use2[i] == 1)
        P[i] = ++Max;
        else
            P[i] = P[i - 1];
        Max = max(Max, P[i]);
    }

}
int Query(int ind, int i, int poz)
{
    int ans = 0;
    while(poz >= 1)
    {
        ans += S[ind][i][poz];
        if(ans >= MOD)
            ans -= MOD;
        poz -= (poz & (-poz));
    }
    return ans % MOD;
}

void Update(int ind,int i, int poz, int val)
{
    while(poz <= Max)
    {
        S[ind][i][poz] += val;
        if(S[ind][i][poz] >= MOD)
            S[ind][i][poz] -= MOD;
        poz += (poz & (-poz));
    }
}
void Solve()
{
    int ind = 0;
    DP[0][0][0] = 1;
    //Update(0, 1, 1);
    S1[0] = S2[0] = 0;
    Partial[0][0][0] = 1;
    for(int i = 1; i <= N; i++)
        Partial[0][i][0] = 1;
    for(int k = 0; k <= p; k++, ind = 1 - ind)
    {
        for(int j = 0; j <= Max; j++)
            S[ind][0][j] = S[1 - ind][0][j] = 0;
        for(int i = 1; i <= N; i++)
        {
            if(k == 0)
                Update(ind, i - 1, 1, 1);
            if(k == 1)
                Update(1 - ind,i - 1, 1, 1);
            int x = Query(ind, i, 1);
            Update(ind, i, 1, -x);
            x = Query(1 - ind, i, 1);
            Update(1 - ind, i, 1, -x);
            for(int j = 1; j <= M; j++)
            {
                if(P[j] != P[j - 1])
                {
                    int x = Query(ind, i, P[j]);
                    Update(ind, i, P[j], -x);
                    x = Query(1 - ind, i, P[j]);
                    Update(1 - ind, i, P[j], -x);
                }

                DP[ind][i][j] = 0;
                Partial[ind][i][j] = Partial[ind][i - 1][j];
                /*int a = Query(S[ind][j]);
                Update(ind, j, -Query(S[in]))*/

                if(S1[i] != S2[j])
                {
                    if(k > 0)
                        Update(1 - ind, i - 1, P[S2[j]], Partial[1 - ind][i - 1][j]);
                    Update(ind, i - 1, P[S2[j]], Partial[ind][i - 1][j]);
                    continue;
                }

                int add = ind;
                if(k > 0 && S1[i] == S3[k])
                    add = 1 - ind;

                DP[ind][i][j] = Query(add, i - 1, P[S2[j]]);

                Partial[ind][i][j] = Partial[ind][i - 1][j];
                Partial[ind][i][j] += DP[ind][i][j];
                if(Partial[ind][i][j] >= MOD)
                    Partial[ind][i][j] -= MOD;
                if(k == p)
                    res += DP[ind][i][j];
                if(res >= MOD)
                    res -= MOD;
                if(k > 0)
                    Update(1 - ind, i - 1, P[S2[j]], Partial[1 - ind][i - 1][j]);
                Update(ind, i - 1, P[S2[j]], Partial[ind][i - 1][j]);

            }
        }
    }
    g << res << "\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}