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

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

char a[501],b[501];
int i,j,la,lb,max,nr,mat[501][501];

int main(){
f.getline(a,501);
la=strlen(a);
f.getline(b,501);
lb=strlen(b);

for(i=0;i<=la-1;i++)
    if(b[0]==a[i])
      for(j=i+1;j<=la;j++)
	  mat[1][j]=1;

for(j=0;j<=lb-1;j++)
     if(a[0]==b[j])
	for(i=j+1;i<=lb;i++)
	   mat[i][1]=1;

for(i=1;i<=la-1;i++)
   for(j=1;j<=lb-1;j++)
       if(a[i]==b[j])
	 {  if(mat[j-1][i-1]>mat[j-1][i])
		 max=mat[j-1][i-1];
	       else
		 max=mat[j-1][i];
	       if(mat[j][i-1]>max)
		  max=mat[j][i-1];

	   if(a[i-1]==b[j-1])
	      mat[i][j]=max;
	    else
	      if(a[i+1]==b[j+1])
		mat[i][j]=max+1;
	   }
max=0;
for(i=1;i<=lb;i++)
   for(j=1;j<=la;j++)
      if(mat[i][j]>max)
	max=mat[i][j];
nr=max;
nr=nr%666013;
g<<nr;
f.close();
g.close();
return 0;
}