#include <stdio.h>   
#include <string.h>   
#define M 666013   
  
long n,m,i,j;   
char x[501],y[501];   
long c[501][501],nr[501][501];   
  
 int main()   
 {   
  freopen("subsir.in","r",stdin);   
  freopen("subsir.out","w",stdout);   
  
  scanf("%s", x+1);   
  scanf("%s", y+1);
     
  m=strlen(x+1);   
  n=strlen(y+1);
    
  for (i=0;i<=m;i++) nr[0][i]=1;   
  for (i=0;i<=n;i++) nr[i][0]=1;   
  
  for (i=1;i<=m;i++)   
      for (j=1;j<=n;j++)   
         if (x[i]==y[j])   
             {   
                c[i][j]=c[i-1][j-1]+1;   
                nr[i][j]=nr[i-1][j-1]%M;   
             }   
          else  
             if (c[i][j-1]>c[i-1][j]) {   
                                       c[i][j]=c[i][j-1];   
                                       nr[i][j]=nr[i][j-1]%M;   
                                      }   
          else  
             if (c[i-1][j]>c[i][j-1])   
                    {   
                        c[i][j]=c[i-1][j];   
                        nr[i][j]=nr[i-1][j]%M;   
                    }   
          else  
            {   
                c[i][j]=c[i-1][j];   
                nr[i][j]=(nr[i][j-1]+nr[i-1][j])%M;   
                if (c[i-1][j-1]==c[i-1][j])   
                    nr[i][j]=(nr[i][j]-nr[i-1][j-1]+M)%M;   
            }   
      
  printf("%ld\n", nr[m][n]);   
  
  return 0;   
}