#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;   
}