#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<=n;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;
		ns[0][0]=1;
	  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;
				xx=ra[i-1][a[i]-65];
				yy=rb[j-1][a[i]-65];
					 if(s [ xx ] [ yy ]== s[i][j]-1)
						  ns[i][j]=(ns[i][j]+(ns[ xx ] [ yy ]==0?1:ns[ xx ] [ yy ] ))%NR;
			 }

		 }
  sum=0;

  for(k='a';k<='z';k++)
  {
  xx=0; yy=0;
  for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
		if(a[i]==k && ns[i][j] && 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\n",sum);
	  fclose(g);
}

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