#include <bits/stdc++.h>
using namespace std;

ifstream in ( "pedefe.in"  );
ofstream out( "pedefe.out" );

const int DIM = 5e2 + 5;
const int MOD = 666013;

int dp[2][DIM][DIM], cnt[DIM], n, m, p, ans;
int a[DIM], b[DIM], c[DIM], bit[DIM];

void add( int &x, int y ) {
    x += y;

    if( x >= MOD )
        x -= MOD;

    return;
}

void update( int pos, int val ) {
    for( int i = pos; i < DIM; i += (i & (-i)) )
        add( bit[i], val );
    return;
}

int query( int pos ) { int val = 0;
    for( int i = pos; i > 0; i -= (i & (-i)) )
        add( val, bit[i] );
    return val;
}

int main( void ) {

    in >> n >> m >> p;
    for( int i = 1; i <= n; i ++ ) in >> a[i];
    for( int j = 1; j <= m; j ++ ) in >> b[j];
    for( int k = 1; k <= p; k ++ ) in >> c[k];

    dp[0][0][0] = 1;
    for( int k = 0, l = 0; k <= p; k ++, l = 1 - l ) {
        for( int i = 1; i <= n; i ++ )
            memset( dp[1 - l][i], 0, sizeof( dp[1 - l][i] ) );

        for( int i = 1; i <= n; i ++ ) {
            memset( bit, 0, sizeof(bit) );

            if( k == 0 )
                update( 2, 1 );

            for( int j = 1; j <= m; j ++ ) {
                if( a[i] == b[j] ) {
                    if( k < p && a[i] == c[k + 1] )
                        add( dp[1 - l][i][j], query(a[i] + 1) );
                    else
                        add( dp[l - 0][i][j], query(a[i] + 1) );
                }

                if( k == p )
                    add( ans, dp[l][i][j] );

                update( b[j] + 1, cnt[j] );
                add( cnt[j], dp[l][i][j] );
            }
        }

        for( int j = 1; j <= m; j ++ )
            cnt[j] = 0;
    }

    out << ans;
    return 0;
}