#include<stdio.h>
#include<string.h>
char a[505],b[505],c;
long n,m,i,j,mat[505][505],nr[505][505],la[256],lb[256],matt[256],s=0,max;
int main()
{
 freopen("subsir.in","r",stdin);
 freopen("subsir.out","w",stdout);
 gets(a);
 scanf("\n");
 gets(b);
 n=strlen(a);
 m=strlen(b);
 for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
       if(a[i-1]==b[j-1])mat[i][j]=mat[i-1][j-1]+1;
         else if(mat[i-1][j]>mat[i][j-1])mat[i][j]=mat[i-1][j];
                                    else mat[i][j]=mat[i][j-1];
 for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
       if(max<mat[i][j])max=mat[i][j];
 for(i=1;i<=n;++i)
    {for(j=1;j<=m;++j)
        {if(a[i-1]==b[j-1])
           {for(c='a';c<='z';++c)
               if(la[c]&&lb[c])
                 if(mat[i][j]==mat[la[c]][lb[c]]+1)nr[i][j]=(nr[i][j]+nr[la[c]][lb[c]])%666013;
            if(matt[a[i-1]]<nr[i][j]&&mat[i][j]==max){s=(s-matt[a[i-1]]+nr[i][j])%666013;matt[a[i-1]]=nr[i][j];}
           }
         lb[b[j-1]]=j;
         if(nr[i][j]==0)nr[i][j]=1;}
     memset(lb,0,sizeof(lb));
     la[a[i-1]]=i;}
 printf("%ld",s);
 return 0;
}