#include<cstdio>
const int N=1<<9;
const int MOD=666013;
int lung,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;
                if(A[i-1][j-1]==0) B[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(char c='a';c<='z';c++)
    {
        for(int i=1;a[i];i++)
            if(a[i]==c)
                la[c-'a'+1][i]=i;
            else
                la[c-'a'+1][i]=la[c-'a'+1][i-1];
        for(int i=1;b[i];i++)
            if(b[i]==c)
                lb[c-'a'+1][i]=i;
            else
                lb[c-'a'+1][i]=lb[c-'a'+1][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-1][y-1])%MOD;
                }
                if(!B[i][j]) B[i][j]=1;
            }
}
void rasp()
{
    int rez=0;
    for(int i=1;a[i];i++)
        for(int j=1;b[j];j++)
            if(A[i][j]==lung && B[i][j] && f[a[i]-'a'+1][b[j]-'a'+1]==false)
            {
                rez=(rez+B[i][j])%MOD;
                f[a[i]-'a'+1][b[j]-'a'+1]=true;
            }
    printf("%d",rez);
}
void afis(int A[N][N])
{
    for(int i=1;a[i];i++)
    {
        for(int j=1;b[j];j++)
            printf("%d",A[i][j]);
        printf("\n");
    }
}
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    gets(a+1);
    gets(b+1);
    cmlsc();
    pregen();
    solve();
    rasp();
    return 0;
}