//BMC
#include<string.h>
#include<iostream.h>
ifstream fin("subsir.in");
ofstream fout("subsir.out");

int mx(int a,int b)
{ if(a>b)return a;
  else return b;
}

int main()
{ int m[502][502],i,j,n1,n2;
  long max=0,nr=0;
  char c1[501],c2[502];
  fin>>c1>>c2;
  n1=strlen(c1);
  n2=strlen(c2);
  for(i=0;i<=n1;i++)m[i][0]=0;
  for(i=0;i<=n2;i++)m[0][i]=0;
  for(i=1;i<=n1;i++)
  for(j=1;j<=n2;j++)
    if(c1[i-1]==c2[j-1])
     { m[i][j]=m[i-1][j-1]+1;
       if(m[i][j]>max){max=m[i][j];nr=0;}
       if(m[i][j]==max)nr=(nr+1)%666013;
     }
   else m[i][j]=mx(m[i][j-1],m[i-1][j]);
 fout<<nr<<'\n';
 return 0;
}