#include<cstdio>
#include<cstring>
char x[503],y[503],c;
int i,j,n,m,s[503][503],r[503][503],u[503][27],v[503][27],t,a,b,d[27],e[27];
int main()
{freopen("subsir.in","r",stdin),freopen("subsir.out","w",stdout);
gets(x),gets(y),n=strlen(x),m=strlen(y);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
     s[i][j]=(a=s[i-1][j]>s[i][j-1]?s[i-1][j]:s[i][j-1])>(b=s[i-1][j-1]+((x[i-1]==y[j-1])?1:0))?a:b;
for(c='a';c<='z';c++)
     {for(i=1;i<=n;i++)
     if(x[i-1]==c)
             u[i][c-'a']=i;     
     else
             u[i][c-'a']=u[i-1][c-'a'];
     for(i=1;i<=m;i++)
     if(y[i-1]==c)
             v[i][c-'a']=i;
     else
             v[i][c-'a']=v[i-1][c-'a'];}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i-1]==y[j-1]&&s[i][j]==1)
     r[i][j]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i-1]==y[j-1])
     for(c='a';c<='z';c++)
     if(s[i][j]==s[u[i-1][c-'a']][v[j-1][c-'a']]+1)
            r[i][j]=(r[i][j]+r[u[i-1][c-'a']][v[j-1][c-'a']])%666013;
for(c='a';c<='z';c++)
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i-1]==c&&y[j-1]==c&&i!=j&&i<n&&j<m)
     d[c-'a']=i,e[c-'a']=j;
for(c='a';c<='z';c++)
     t=(t+r[d[c-'a']][e[c-'a']])%666013;
printf("%d",t);
return 0;}