#include<fstream.h>
#include<string.h>

ifstream f("date.in");
ofstream g("date.out");

char x[100],y[100];
int lx,ly,a[100][100],i,j,nr,max;

int main(){
f.getline(x,100);
lx=strlen(x);
f.getline(y,100);
ly=strlen(y);

for(i=0;i<=lx-1;i++)
{  if(x[i]==y[1])
    for(j=i+1;j<=lx;j++0
       mat[1][j]=1;
   break;
}

for(i=0;i<=ly-1;i++)
 {   if(x[1]==y[j])
      for(j=i+1;j<=ly;j++)
	 mat[j][1]=1;
  break;
 }

 for(i=1;i<=ly-1;i++)
    for(j=1;j<=lx-1;j++)
       {  if(a[i-1][j-1]>a[i-1][j])
	      max=a[i-1][j-1];
	    else
	      max=a[i-1][j];
	   if(a[i][j-1]>max)
	      max=a[i][j-1];

	   if(x[j]==y[i])
	     if(x[j-1]==y[i-1])
		 a[i][j]=max;
	       else
		 if(x[j+1]==y[i+1])
		      a[i][j]=max+1;
		    else
		      a[i][j]=max;
	    else
	       a[i][j]=max;
	  }

max=a[lx][ly];
max=max%666013;
g<<max;