#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char a[512],b[512];
long i,j,n,m,c[512][512],nr[512][512],pa[512][30],pb[512][30],ii,jj,rez,k;
long maxim(long a,long b)
{
    if (a>b)
    return a;
    return b;
}
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%s",a);
    scanf("%s",b);
    n=strlen(a);
    m=strlen(b);
    for(i=n-1;i>=0;i--)
    a[i+1]=a[i]-96;
    for(i=m-1;i>=0;i--)
    b[i+1]=b[i]-96;
    for(i=2;i<=n+1;i++)
    {
        for(j=1;j<=26;j++)
        pa[i][j]=pa[i-1][j];
        pa[i][a[i-1]]=i-1;
        }
        for(i=2;i<=m+1;i++)
        {
            for(j=1;j<=26;j++)
            pb[i][j]=pb[i-1][j];
            pb[i][b[i-1]]=i-1;
        }
        if(a[1]==b[1])
        {
            c[1][1]=1;
            nr[1][1]=1;
        }
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if((i!=1)||(j!=1))
        if(a[i]==b[j])
        {
            c[i][j]=c[i-1][j-1]+1;
            if(c[i][j]==1)
            nr[i][j]=1;
        }
        else
        c[i][j]=maxim(c[i][j-1],c[i-1][j]);
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(a[i]==b[j])
        for(k=1;k<=26;k++)
        {
            ii=pa[i][k];
            jj=pb[j][k];
            if((c[ii][jj]+1)==c[i][j])
            {
                nr[i][j]+=nr[ii][jj];
                nr[i][j]=nr[i][j]%666013;
            }
        }
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if((c[i][j]==c[n][m])&&(pa[n+1][a[i]]==i)&&(pb[m+1][b[j]]==j))
        {
            rez+=nr[i][j];
            rez=rez%666013;
        }
        printf("%d\n",rez);
        return 0;
}