#include<cstdio>
const int N=1<<9;
const int MOD=666013;
int lung,n,m,last1[1<<5],last2[1<<5],la[1<<5][N],lb[1<<5][N],A[N][N],B[N][N];
char a[N],b[N];
bool f[1<<5][1<<5];
int max(int x,int y)
{
    return x>y?x:y;
}
void cmlsc()
{
    for(int i=1;a[i];i++)
        for(int j=1;b[j];j++)
            if(a[i]==b[j])
                A[i][j]=A[i-1][j-1]+1;
            else
                A[i][j]=max(A[i-1][j],A[i][j-1]);
    for(int i=1;a[i];i++)
        for(int j=1;b[j];j++)
            if(A[i][j]>lung)
                lung=A[i][j];
}
void pregen()
{
    for(int c=1;c<=26;c++)
    {
        int i=0;
        for(i=1;a[i];i++)
            if(a[i]==c+'a'-1)
                la[c][i]=i;
            else
                la[c][i]=la[c][i-1];
        last1[c]=la[c][i-1];
        n=i-1;
        i=0;
        for(i=1;b[i];i++)
            if(b[i]==c+'a'-1)
                lb[c][i]=i;
            else
                lb[c][i]=lb[c][i-1];
        last2[c]=lb[c][i-1];
        m=i-1;
    }
}
void solve()
{
    for(int i=1;a[i];i++)
        for(int j=1;b[j];j++)
            if(a[i]==b[j])
            {
                for(int c=1;c<=26;c++)
                {
                    int x=la[c][i-1];
                    int y=lb[c][j-1];
                    if((!x)||(!y)) continue;
                    if(A[i][j]==A[x][y]+1)
                        B[i][j]=(B[i][j]+B[x][y])%MOD;
                }
                if(!B[i][j]) B[i][j]=1;
            }
}
void rasp()
{
    int rez=0;
    for(int c=1;c<=26;c++)
    {
        int i1=last1[c],i2=last2[c];
        if(A[i1][i2]==lung && i1 && i2)
        {
            rez+=B[i1][i2];
            rez%=MOD;
        }
    }
    printf("%d",rez);
}
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    gets(a+1);
    gets(b+1);
    cmlsc();
    pregen();
    solve();
    rasp();
    return 0;
}