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

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

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

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

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

}

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

 }

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

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

max=a[ly][lx];
max=max%666013;
g<<max;
f.close();
g.close();
return 0;}