#include<stdio.h>
#include<string.h>
using namespace std;

int main(){
    FILE *f=fopen("subsir.in","r");
    FILE *g=fopen("subsir.out","w");
    char s1[501],s2[501];
    long nr[501][501],l[501][501];
    int n1,n2,i,j;
    long mod=666013;
    fscanf(f,"%s%s",s1,s2);
    n1=strlen(s1);
    n2=strlen(s2);
    //fprintf(g,"%s%s",s1,s2);
    for(i=0;i<n1;i++)
        {nr[i][0]=0;l[i][0]=0;}
      //  fprintf(g,"%d%d",n1,n2);
    for(j=0;j<n2;j++)
        {nr[0][j]=0;l[0][j]=0;}
    for(i=1;i<n1;i++)
         for(j=1;j<n2;j++)  
              if(s1[i]==s2[j]){
                   if(nr[i-1][j-1]>0)
                       nr[i][j]=nr[i-1][j-1];
                   else
                       nr[i][j]=1;    
                   l[i][j]=l[i-1][j-1]+1;
              }
              else
                  if(l[i-1][j]>l[i][j-1]){
                       l[i][j]=l[i-1][j];
                       nr[i][j]=nr[i-1][j];
                  }   
                  else
                      if(l[i-1][j]<l[i][j-1]){
                            l[i][j]=l[i][j-1];
                            nr[i][j]=nr[i][j-1];
                      }                             
                      else{
                           l[i][j]=l[i-1][j];
                           //nr de subsiruri care nu contin yj=nr[i][j-1] 
                           //nr de subsiruri care nu contin xi=nr[i-1][j]
                           //comun - nr celor care contin pe ambele xi si yj = nr[i-1][j-1], asta daca l[i-1][j-1]=l[i][j] 
                           
                           if(l[i-1][j-1]==l[i-1][j]) //subsirurile optime nu contin xi si yj
                               nr[i][j]=(nr[i-1][j]+nr[i][j-1]-nr[i-1][j-1])%mod;
                           else    
                               nr[i][j]=(nr[i-1][j]+nr[i][j-1])%mod;
                      }
      fprintf(g,"%ld",nr[n1-1][n2-1]%mod);
     // fprintf(g,"%ld",l[n1-1][n2-1]);        
      fclose(f);
      fclose(g);       
      return 0;
}