#include <string.h>
#include <stdio.h>
#define N 501
#define mod 666013
int mat[N][N];
int sum[N][N];
int a1[N],a2[N],*p1=a1,*p2=a2;
char sir1[N],sir2[N];
int alph1[N][26],alph2[N][26];
int main ()
{freopen("subsir.in","r",stdin);
 freopen("subsir.out","w",stdout);
 
 int i,j,k,n,m,max,*aux,s;
 fgets(sir1,501,stdin);
 fgets(sir2,501,stdin);
 n=strlen(sir1);
 m=strlen(sir2);
 if(sir1[n-1]=='\n')n--;
 for (i=n;i>=1;i--)
 {sir1[i]=sir1[i-1];}

 for (i=m;i>=1;i--)
 {sir2[i]=sir2[i-1];}

 for (i=1;i<=n;i++)
 {for (j=0;j<26;j++)
  {if(sir1[i]-'a'!=j)
    alph1[i][j]=alph1[i-1][j];
   else
    alph1[i][j]=i;
  }
 }

 for (i=1;i<=m;i++)
 {for (j=0;j<26;j++)
  {if(sir2[i]-'a'!=j)
    alph2[i][j]=alph2[i-1][j];
   else
    alph2[i][j]=i;
  }
 }
 /*
 for (k=0;k<26;k++)
 {for (i=1;i<=n;i++)
  {printf("%d ",alph1[i][k]);
  }
  printf("\n");
 } */
 max=0;
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {if(sir1[i]==sir2[j])
   {mat[i][j]=p1[j-1]+1;

    if(max<mat[i][j])
    {max=mat[i][j];
    }
    if(p2[j-1]>p1[j-1]+1)
    {p2[j]=p2[j-1];
    }
    else
    {p2[j]=p1[j-1]+1;
    }
   }
  }
  aux=p2;p2=p1;p1=aux;
 }
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {if(mat[i][j]==1)
   {sum[i][j]=1;
   }
  }
 }
 
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {if(mat[i][j])
   {for (k=0;k<26;k++)
    {if(mat[alph1[i-1][k]][alph2[j-1][k]]==mat[i][j]-1)
     {sum[i][j]=(sum[i][j]+sum[alph1[i-1][k]][alph2[j-1][k]])%mod;
     }
    }
   }
  }
 }
  /*
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {printf("%d",mat[i][j]);
  }
  printf("\n");
 }  */
 s=0;
 for (k=0;k<26;k++)
 {if(mat[alph1[n][k]][alph2[m][k]]==max)
  {s=(s+sum[alph1[n][k]][alph2[m][k]])%mod;
  }
 }
 
 printf("%d",s);
 return 0;
}