#include<stdio.h>
#include<string.h>

#define NMAX 503
#define MOD 666013

char a[NMAX],b[NMAX];
int numarat[26];
int ua[26][NMAX],ub[26][NMAX],nr[NMAX][NMAX],c[NMAX][NMAX];
int la,lb,i,j,k,ii,jj,lmax,rez;

int max(int x,int y) {
  return x>y?x:y;
}

int main() {
  freopen("subsir.in","r",stdin);
  freopen("subsir.out","w",stdout);
  fgets(a+1,NMAX,stdin);
  fgets(b+1,NMAX,stdin);
  la=strlen(a+1)-1;
  lb=strlen(b+1)-1;

  for(j=1;j<=lb;j++)
   if(a[1]==b[j]) c[1][j]=1;
   else c[1][j]=c[1][j-1];
  lmax=c[1][lb];
  for(i=2;i<=la;i++)
   for(j=1;j<=lb;j++)
    if(a[i]==b[j]) {
      c[i][j]=1+c[i-1][j-1];
      if(c[i][j]>lmax) lmax=c[i][j];
    }
    else c[i][j]=max(c[i-1][j],c[i][j-1]);

  for(i=0;i<26;i++)
   for(j=1;j<=la;j++)
    if(a[j]=='a'+i) ua[i][j]=j;
    else ua[i][j]=ua[i][j-1];
  for(i=0;i<26;i++)
   for(j=1;j<=lb;j++)
    if(b[j]=='a'+i) ub[i][j]=j;
    else ub[i][j]=ub[i][j-1];

  for(i=1;i<=la;i++)
   for(j=1;j<=lb;j++)
    if(a[i]==b[j]) {
      if(c[i][j]==1) nr[i][j]=1;
      else
       for(k=0;k<26;k++) {
         ii=ua[k][i-1];
         jj=ub[k][j-1];
         if(c[i][j]==c[ii][jj]+1) {
           nr[i][j]+=nr[ii][jj];
           nr[i][j]%=MOD;
         }
       }
     }
  for(i=la;i>=1;i--)
   for(j=lb;j>=1;j--)
    if(nr[i][j]&&c[i][j]==lmax&&!numarat[a[i]-'a']) {
      rez+=nr[i][j];
      rez%=MOD;
      numarat[a[i]-'a']=1;
    }
  printf("%d\n",rez);
  return 0;
}