#include<stdio.h>
#include<string.h>
#define LMAX 505
#define RTT 666013
FILE *f=fopen("subsir.in","r"), *g=fopen("subsir.out","w");

long int La, Lb, Rnr=0, Rlu=0;
long int PDnr[LMAX][LMAX], PDlu[LMAX][LMAX];
long int aNext[LMAX][30], bNext[LMAX][30];
long int aNext2[LMAX], bNext2[LMAX];
char a[LMAX], b[LMAX];

    // PDnr[i][j] = numarul de posibilitati de lungime PDlu[i][j]
    // Next[poz][char] = Urmatoarea pozitia a fiecarui caracter (in stanga)
    // Next2 -"- (in dreapta)

long int Maxim( long int A, long int B ){ if(A>B)return A; return B; }
long int Minim( long int A, long int B ){ if(A<B)return A; return B; }

void Citire(){
    fscanf(f,"%s\n",a+1); La = strlen(a+1);
    fscanf(f,"%s\n",b+1); Lb = strlen(b+1);
}

void Creare_Next(){
long int i, j;

    for(i=1;i<=La;i++) aNext[i+1][ a[i]-'a' ] = i;
    for(i=1;i<=Lb;i++) bNext[i+1][ b[i]-'a' ] = i;

    for(i=1;i<=La;i++)
        for(j=0;j<=25;j++)
            aNext[i][j] = Maxim( aNext[i][j], aNext[i-1][j] );

    for(i=1;i<=Lb;i++)
        for(j=0;j<=25;j++)
            bNext[i][j] = Maxim( bNext[i][j], bNext[i-1][j] );

    for(i=1;i<=La;i++) aNext2[i] = La + 1;
    for(i=1;i<=Lb;i++) bNext2[i] = Lb + 1;

    for(i=1;i<=La;i++)
        for(j=i+1;j<=La;j++)
            if( a[i] == a[j] ){ aNext2[i] = j; break; }

    for(i=1;i<=Lb;i++)
        for(j=i+1;j<=Lb;j++)
            if( b[i] == b[j] ){ bNext2[i] = j; break; }

}

void Rezolvare(){
long int i, j, poza, pozb, lit, NEWnr, NEWlu, MAXnr, MAXlu;


    for(i=1;i<=La;i++)
    for(j=1;j<=Lb;j++)
    if( a[i] == b[j] ){

        MAXnr = 0; MAXlu = 0;

        for(lit=0;lit<=25;lit++){

            poza = aNext[i][lit];
            pozb = bNext[j][lit];

            NEWnr = PDnr[poza][pozb];
            NEWlu = PDlu[poza][pozb];

            if( NEWlu > MAXlu ){ MAXlu = NEWlu; MAXnr = NEWnr; }
            else if( NEWlu == MAXlu && MAXlu != 0 ){ MAXnr += NEWnr; }

        }

        if( MAXlu == 0 ) MAXnr = 1;

        PDnr[i][j] = MAXnr % RTT;
        PDlu[i][j] = MAXlu + 1;

        if( aNext2[i] == La + 1 && bNext2[j] == Lb + 1 ){
            if( PDlu[i][j] > Rlu ){ Rlu = PDlu[i][j]; Rnr = PDnr[i][j]; }
            else if( PDlu[i][j] == Rlu ){ Rnr += PDnr[i][j]; Rnr %= RTT;}
        }

    }

    fprintf(g,"%ld\n",Rnr);
    // printf("%ld\n",Rlu);

}

int main(){

    Citire();
    Creare_Next();
    Rezolvare();

return 0;
}