#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[PMax][NMax];
int Arb[2][NMax];
int res = 0;
int Partial[2][NMax][NMax];
vector <int> V;
int Use[NMax], Use2[NMax];
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;
    for(int i = 1; i <= 500; i++)
    {
        if(Use[i] == 1 && Use2[i] == 1)
            V.push_back(i), P[i] = V.size() + 1;
        else
            P[i] = P[i - 1];
    }

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

void Update(int ind, int poz, int val)
{
    int sz = V.size();
    while(poz <= sz + 1)
    {
        S[ind][poz] += val;
        if(S[ind][poz] >= MOD)
            S[ind][poz] -= MOD;
        poz += (poz & (-poz));
    }
}
void Solve()
{
    int ind = 0;
    DP[0][0][0] = 1;
    //Update(0, 1, 1);
    S1[0] = S2[0] = 0;
    for(int k = 0; k <= p; k++, ind = 1 - ind)
    {

        for(int i = 0; i <= N; i++)
        {
            for(int j = 0; j <= M; j++)
            {
                if(k == 0 && i == 0 && j == 0)
                {
                    if(i > 0)
                    Partial[ind][i][j] = Partial[ind][i - 1][j];
                else
                    Partial[ind][i][j] = 0;
                Partial[ind][i][j] += DP[ind][i][j];
                if(Partial[ind][i][j] >= MOD)
                    Partial[ind][i][j] -= MOD;
                    Update(0, 1, 1);
                    continue;
                }

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

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

                    continue;
                }

                int add = 0;
                if(k > 0 && S1[i] == S3[k])
                    add = 1;
                if(add == 1)
                    add = k - 1;
                else
                    add = k;
                DP[ind][i][j] = Query(add, P[S2[j]]);
                if(i > 0)
                    Partial[ind][i][j] = Partial[ind][i - 1][j];
                else
                    Partial[ind][i][j] = 0;
                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 && i > 0)
                    Update(k - 1, P[S2[j]], Partial[1 - ind][i - 1][j]);
                if(i > 0)
                    Update(k, P[S2[j]], Partial[ind][i - 1][j]);

            }
            for(int j = 0; j <= V.size() + 1; j++)
                S[k][j] = S[k - 1][j] = 0;
        }
    }
    g << res << "\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}