#include <stdio.h>
#include <string.h>
#define sigma 26

char a[505],b[505];
long n,m,i,j,k,ok;
unsigned char C[505][505];
long lasti[26][505],lastj[26][505];
long v[505][505],lcs,lcs_nr;

void cmlsc(){
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (a[i]==b[j])
               C[i][j]=C[i-1][j-1]+1;
            else if (C[i-1][j]>C[i][j-1])
                    C[i][j]=C[i-1][j];
                 else C[i][j]=C[i][j-1];
    lcs=C[n][m];
}

void preproc(){
     for (i=1;i<=n;i++){
         for (j=0;j<sigma;j++)
             lasti[j][i]=lasti[j][i-1];
         lasti[a[i]-'a'][i]=i;
     }
     for (i=1;i<=m;i++){
         for (j=0;j<sigma;j++)
             lastj[j][i]=lastj[j][i-1];
         lastj[b[i]-'a'][i]=i;
     }      
}

void solve(){
     //matrice cu nr de lcs pentru A[1....i] si B[1.....j]
     for (i=1;i<=n;i++)
         for (j=1;j<=m;j++)
             if (a[i]==b[j]){
                ok=0;
                for (k=0;k<sigma;k++)
                    if (lasti[k][i-1]&&lastj[k][j-1]){
                       ok=1;
                       if (C[i][j]==C[lasti[k][i-1]][lastj[k][j-1]]+1){
                          v[i][j]+=v[lasti[k][i-1]][lastj[k][j-1]];
                          v[i][j]%=666013;
                       }
                    }
                if (!ok)v[i][j]=1;
             }
     //Numasr total de lcs
     for (i=1;i<=n;i++)
         for (j=1;j<=m;j++)
             if (C[i][j]==lcs)
                if (a[i]==b[j]){
                   ok=1;
                   for (k=i+1;k<=n;k++)
                       if (a[i]==a[k]){ok=0;break;}
                   for (k=j+1;k<=m;k++)
                       if (b[j]==b[k]){ok=0;break;}
                   if (ok){lcs_nr+=v[i][j];lcs_nr%=666013;}
                }
}

int main(){
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);

    scanf("%s\n%s",a+1,b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    
    cmlsc();
    preproc();
    solve();
  
    printf("%ld\n",lcs_nr);
    
return 0;
}