#include<stdio.h>
#include<string.h>
FILE*f=fopen("subsir.in","r");
FILE*g=fopen("subsir.out","w");
char x[1024], y[1024];
long n,m;
char last;
long l[512][512],lmax,Sol=1;
void dinamic()
  {
  int i,j,h,p;
  last='!';
  for(i=1;i<=n;++i)

   for(j=1;j<=m;++j)
      if(x[i]==y[j])
	{
	l[i][j]=1+l[i-1][j-1];
	if(l[i][j]==lmax && x[i]!=last ) Sol=(Sol+1)%666013;
	else if(l[i][j]>lmax) lmax=l[i][j],Sol=1,last=x[i];
	}
      else
      if(l[i][j-1]>l[i-1][j]) l[i][j]=l[i][j-1];
      else l[i][j]=l[i-1][j];
  fprintf(g,"%ld\n",Sol);
  }
int main()
  {          char c;
  int i;
  n=0;
  do
   {
   fscanf(f,"%c",&c);
   if(c=='\n') break;
   else x[++n]=c;
   }
  while(c!='\n');
  do
  {
  fscanf(f,"%c",&c);
  if(c=='\n') break;
  else y[++m]=c;
  }
  while(c!='\n');
  dinamic();
  return 0;
  }