#include<stdio.h>
#include<string.h>
#define NR 666013
char a[502],b[502];
int n,m,s[502][502],ra[502][30],rb[502][30];
long ns[502][502],sum;
void READ()
{    int i;
	  FILE *f;
	  f=fopen("subsir.in","r");
	  fscanf(f,"%s",&a);
	  n=strlen(a);

	  for(i=n;i>0;i--)
		 a[i]=a[i-1];
	  fscanf(f,"%s",&b);
	  m=strlen(b);

	  for(i=m;i>0;i--)
		 b[i]=b[i-1];
	  fclose(f);
}

void BUILD()
{ int i,j;
  for(i=1;i<=n;i++)
 {
	for(j='a'-65;j<='z'-65;j++)
	  ra[i][j]=ra[i-1][j];
	ra[i][a[i]-65]=i;
 }
 for(i=1;i<=m;i++)
 {
	for(j='a'-65;j<='z'-65;j++)
	  rb[i][j]=rb[i-1][j];
	rb[i][b[i]-65]=i;
 }
}


void SOLVE()
{ int i,j,xx,yy,k;
	  for(i=1;i<=n;i++)
		 for(j=1;j<=m;j++)
		 {
			 if(a[i]==b[j])
			 {
				s[i][j]=s[i-1][j-1]+1;

				for(k='a';k<='z';k++)
				{  xx=ra[i-1][k-65];
					yy=rb[j-1][k-65];
					 if(s [ xx ] [ yy ]== s[i][j]-1)
						  ns[i][j]=(ns[i][j]+ns[ xx ] [ yy ])%NR;

				  }
				if(s[i][j]==1) ns[i][j]=1;
			 }
			else  s[i][j]=(s[i-1][j]>s[i][j-1]?s[i-1][j]:s[i][j-1]);

		 }
  sum=0;

  for(k='a';k<='z';k++)
  {
  xx=0; yy=0;
  for(i=n;i>=1;i--)
	 for(j=m;j>=1;j--)
		if(a[i]==k && ns[i][j] && s[i][j]==s[n][m] && i>xx && j>yy)
		{
			sum=(sum+ns[i][j])%NR;
			xx=i; yy=j;
		}
  }


}

void PRINT()
{
	  FILE *g;
	  g=fopen("subsir.out","w");
	  fprintf(g,"%ld",sum);
	  fclose(g);
}

int main()
{
READ();
BUILD();
SOLVE();
PRINT();
return 0;
}