#include <fstream>
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];
const int MOD = 666013;
void Read()
{
    f >> N >> M >> P;
    for(int i = 1; i <= N; i++)
        f >> S1[i];
    for(int i = 1; i <= M; i++)
        f >> S2[i];
    for(int i = 1; i <= P; i++)
        f >> S3[i];
}
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)
{
    while(poz <= 501)
    {
        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] || (k == 0 && S1[i] == S3[1]))
                {
                     if(k > 0)
                    Update(k - 1, S2[j] + 1, Partial[1 - ind][i - 1][j]);
                if(i > 0)
                    Update(k, S2[j] + 1, 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, S2[j] + 1);
                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)
                    Update(k - 1, S2[j] + 1, Partial[1 - ind][i - 1][j]);
                if(i > 0)
                    Update(k, S2[j] + 1, Partial[ind][i - 1][j]);

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