#include <string.h>
#include <stdio.h>
#define N 511
#define mod 666013
int mat[N][N];
int sum[N][N];
int a1[N],a2[N],*p1=a1,*p2=a2;
char sir1[N],sir2[N];
int alph1[N][27],alph2[N][27];
int main ()
{freopen("subsir.in","r",stdin);
 freopen("subsir.out","w",stdout);
 
 int i,j,k,n,m,max,*aux,s;
 fgets(sir1,510,stdin);
 fgets(sir2,510,stdin);
 n=strlen(sir1);
 m=strlen(sir2);
 if(sir1[n-1]=='\n')n--;
 for (i=n;i>=1;i--)
 {sir1[i]=sir1[i-1];}

 for (i=m;i>=1;i--)
 {sir2[i]=sir2[i-1];}

 for (i=1;i<=n;i++)
 {for (j=0;j<26;j++)
  {if(sir1[i]-'a'!=j)
    alph1[i][j]=alph1[i-1][j];
   else
    alph1[i][j]=i;
  }
 }

 for (i=1;i<=m;i++)
 {for (j=0;j<26;j++)
  {if(sir2[i]-'a'!=j)
    alph2[i][j]=alph2[i-1][j];
   else
    alph2[i][j]=i;
  }
 }
 max=0;
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {if(sir1[i]==sir2[j])
   {mat[i][j]=p1[j-1]+1;

    if(max<mat[i][j])
    {max=mat[i][j];
    }
    p2[j]=mat[i][j];
   }
   else
   {if(p2[j-1]>p1[j])
    {p2[j]=p2[j-1];}
    else
    {p2[j]=p1[j];
    }
   }
  }
  aux=p2;p2=p1;p1=aux;
 }
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {if(mat[i][j]==1)
   {sum[i][j]=1;
   }
  }
 }
 
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {if(mat[i][j])
   {for (k=0;k<26;k++)
    {if(mat[alph1[i-1][k]][alph2[j-1][k]]==mat[i][j]-1)
     {sum[i][j]=(sum[i][j]+sum[alph1[i-1][k]][alph2[j-1][k]])%mod;
     }
    }
   }
  }
 }
 s=0;
 for (k=0;k<26;k++)
 {if(mat[alph1[n][k]][alph2[m][k]]==max)
  {s=(s+sum[alph1[n][k]][alph2[m][k]])%mod;
  }
 }
 if(max==0)
 {printf("0");
 }
 else
 {printf("%d",s);
 }
 return 0;
}