//subsir
#include<stdio.h>
#include<string.h>
#define max(a,b)((a)>(b)?(a):(b))
FILE*fin=fopen("subsir.in","r");
FILE*fout=fopen("subsir.out","w");
int main()
{
  char a[502],b[502],ch;
  int c[502][502],ua[2][30][502],nr[502][502],n,m,i,j,k,t1,t2,rez=0;
  fscanf(fin,"%s",a);
  fscanf(fin,"%s",b);
  n=strlen(a);
  m=strlen(b);
  //calcul celei mai lungi secv comune
  for(i=0;i<=n;i++)
  {
    c[0][i]=0;
    nr[0][i]=0;
  }
  for(i=1;i<=m;i++)
  {
    c[i][0]=0;
    nr[i][0]=0;
  }
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1]+1;
      else c[i][j]=max(c[i][j-1],c[i-1][j]);
  //calculul ultimei aparitii
  for(i='a';i<='z';i++)
  {
    ua[0][i-'a'][0]=-1;
    ua[1][i-'a'][0]=-1;
    for(j=1;j<=n;j++)
      if(a[j-1]==i) ua[0][i-'a'][j]=j;
      else ua[0][i-'a'][j]=ua[0][i-'a'][j-1];
    for(j=1;j<=m;j++)
      if(b[j-1]==i) ua[1][i-'a'][j]=j;
      else ua[1][i-'a'][j]=ua[1][i-'a'][j-1];
  }
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      if(a[i-1]==b[j-1])
      if(c[i][j]==1) nr[i][j]=1;
      else
      {
	nr[i][j]=0;
	for(k='a';k<='z';k++)
	{
	  t1=ua[0][k-'a'][i-1];
	  t2=ua[1][k-'a'][j-1];
	  if(t1!=-1&&t2!=-1&&(c[t1][t2]+1==c[i][j]))
	    nr[i][j]=(nr[i][j]+nr[t1][t2])%666013;
	}
	ch=a[i-1];
	if(c[i][j]==c[n][m]&&ua[0][ch-'a'][n]==i&&ua[1][ch-'a'][m]==j) rez=(rez+nr[i][j])%666013;
      }
      else nr[i][j]=-1;
  fprintf(fout,"%d",rez);
  fclose(fin);
  fclose(fout);
  return 0;
}