//O(N^2*M^2*P)

#include<iostream>
#include<string>

using namespace std;

#define MOD 666013
#define NM 505

int SOL[NM][NM][2];

int S1[NM],S2[NM],S3[NM];

int main()
{
    int N,M,P;
    
    freopen("pedefe.in","r",stdin);
    freopen("pedefe.out","w",stdout);
    
    scanf("%d %d %d",&N,&M,&P);
    
    for(int i=1;i<=N;++i)
       scanf("%d",&S1[i]);
    
    for(int i=1;i<=M;++i)
       scanf("%d",&S2[i]);
    
    for(int i=1;i<=P;++i)
       scanf("%d",&S3[i]);
    
    SOL[0][0][0]=1;
    
    for(int p=0;p<=P;++p)
    {
        int cur=p%2,prev=!cur;
        
        for(int i=1;i<=N;++i)
           for(int j=1;j<=M;++j)
              SOL[i][j][cur]=0;
        
        for(int i=p;i<=N;++i)
           for(int j=p;j<=M;++j)
              if(S1[i]==S2[j])
                 for(int k=max(p-1,0);k<i;++k)
                    if(S1[k]<=S1[i])
                       for(int l=max(p-1,0);l<j;++l)    
                       {            
                          SOL[i][j][cur]+=SOL[k][l][cur];
                          if(SOL[i][j][cur]>=MOD) SOL[i][j][cur]-=MOD;
                               
                          if(S3[p]==S1[i]) 
                          {
                              SOL[i][j][cur]+=SOL[k][l][prev];
                              if(SOL[i][j][cur]>=MOD) SOL[i][j][cur]-=MOD;             
                          }   
                       }   
         /*              
         for(int i=1;i<=N;++i)
         {
            for(int j=1;j<=M;++j)
               printf("%d ",SOL[i][j][cur]);
            
            printf("\n");   
         }     
         
         printf("\n");                       
         */
    }                  
    
    int ans=0;
    
    for(int i=P;i<=N;++i)
       for(int j=P;j<=M;++j)
       {
          ans+=SOL[i][j][P%2];
          if(ans>=MOD) ans-=MOD;
       }   
       
    printf("%d",ans);
       
    return 0;
}