#include <fstream>
#include <cstring>
using namespace std;
ifstream f("pedefe.in");
ofstream g("pedefe.out");

int n,m,k;
int a[550],b[550],c[550],ab[550],cnt[550] ;
int dp[2][512][512];
#define MOD 666013

inline void add(int &A , int B){
    A += B;
    while( A >= MOD )    A -= MOD;
}

inline void update(int pos,int val){
    for(++pos ; pos < 512 ; pos += pos&-pos)
        add( ab[pos] , val  );
}

inline int query(int pos){
    int sum = 0;
    for(++pos ; pos >0; pos -= pos&-pos)    add(sum , ab[pos]);
    return sum;
}

int main()
{
    f >> n >> m >> k;
    for(int i = 1 ; i <= n ; ++i) f >> a[i];
    for(int i = 1 ; i <= m ; ++i) f >> b[i];
    for(int i = 1 ; i <= k ; ++i) f >> c[i];

    dp[0][0][0] = 1;
    for(int z = 0 ; z <= k ; ++z){
        memset(cnt , 0 , sizeof(cnt) );
        int q = z % 2;
        for(int x = 1; x <= n; ++x){
            memset( ab , 0, sizeof(ab) );
            if( z == 0 )       update( 0 , 1 );
            for(int y = 1; y <= m; ++y){
                dp[1 - q][x][y] = 0;
                if( a[x] == b[y] ){
                    int before = query( a[x] );
                    if( z < k && c[z + 1] == a[x] )
                        add(dp[1-q][x][y] , before);
                    else
                        add(dp[  q][x][y] , before);
                }else
                    dp[q][x][y] = 0;
                update( b[y] , cnt[y] );
                add(  cnt[y] , dp[q][x][y] );
            }
        }
    }
    int sol = 0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            add( sol , dp[k&1][i][j] );
    g << sol;


    return 0;
}