#include<fstream.h>
int max=0;
ofstream fout("subsir.out");
int da,db;
int c[500][500];
char a[500],b[500];

void cit()
{
 int i;
 char c1;
 int luat[27];
  for(i=0;i<=26;i++)
   luat[i]=0;

 ifstream fin("subsir.in");
 da=0;
 c1=fin.get();

 while(c1!='\n')
  {
       //fout<<luat[(int)c1-(int)
   if(luat[(int)c1-(int)'a']==0)
    {
     da++;
     a[da]=c1;
     luat[(int)c1-(int)'a']=1;
    }
   c1=fin.get();

  }

  for(i=0;i<=26;i++)
   luat[i]=0;

   db=0;
 c1=fin.get();

 while(!fin.eof()&&c1!=' '&&c1!='\n')
  {
   if(luat[(int)c1-(int)'a']==0)
    {
     db++;
     b[db]=c1;
     luat[(int)c1-(int)'a']=1;
     //fout<<(int)c1-(int)
    }
   c1=fin.get();

  }


 /* for(i=1;i<=da;i++)
   fout<<a[i];fout<<'\n';
  for(i=1;i<=db;i++)
   fout<<b[i];fout<<'\n';*/



fin.close();
}

/*void afis(int i,int j)
{
 if(i&&j)
  if(t[i][j]==0)
   {
   afis(i-1,j-1);
   fout<<a[i];
   }
    else
     if(t[i][j]==1)
      afis(i-1,j);
       else
	afis(i,j-1);
} */



void rezolvare()
{
 int i,j;
 for(i=1;i<=da;i++)
  for(j=1;j<=db;j++)

   if(a[i]==b[j])
    {

     c[i][j]=1+c[i-1][j-1];
     //t[i][j]=0;
     if(c[i][j]>max)
      max=c[i][j];
    }
     else
      if(c[i-1][j]>c[i][j-1])
       {
	c[i][j]=c[i-1][j];
	//t[i][j]=1;
       }
	else
	 {
	  c[i][j]=c[i][j-1];
	  //t[i][j]=2;
	 }


  /*for(i=1;i<=da;i++)
   {
    for(j=1;j<=db;j++)
     fout<<c[i][j]<<" ";
    fout<<'\n';
   }*/
	  long nr=0;
   for(i=1;i<=da;i++)
    for(j=1;j<=db;j++)
     if(c[i][j]==max)
     {
      nr++;


     }

  fout<<nr%666013<<'\n';

}


void main()
{
 cit();
 rezolvare();
 fout.close();
}