# include <fstream>
# include <cstring>
# define MOD 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
char a[505],b[505],c;
int d[505][505],v[505][505],ua[30][505],ub[30][505],n,m,i,j,k,sol;
int main () {
    fin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i]==b[j])
                v[i][j]=v[i-1][j-1]+1;
            else
                v[i][j]=max(v[i-1][j],v[i][j-1]);
    for(k=1;k<=26;k++){
        c='a'+k-1;
        for(i=1;i<=n;i++)
            if(a[i]==c)
                ua[k][i]=i;
            else
                ua[k][i]=ua[k][i-1];
    }
    for(k=1;k<=26;k++){
        c='a'+k-1;
        for(i=1;i<=m;i++)
            if(b[i]==c)
                ub[k][i]=i;
            else
                ub[k][i]=ub[k][i-1];
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i]==b[j]){
                for(k=1;k<=26;k++)
                    if(a[i]-'a'+1==k){
                        if(v[ua[k][i-1]][ub[k][j-1]]==v[i][j]-1)
                            d[i][j]+=d[ua[k][i-1]][ub[k][j-1]];
                        if(d[i][j]>=MOD)
                            d[i][j]-=MOD;
                    }
                    else{
                        if(v[ua[k][i]][ub[k][j]]==v[i][j]-1)
                            d[i][j]+=d[ua[k][i]][ub[k][j]];
                        if(d[i][j]>=MOD)
                            d[i][j]-=MOD;
                    }
                if(d[i][j]==0)
                    d[i][j]=1;
            }
    for(k=1;k<=26;k++)
        if(v[ua[k][n]][ub[k][m]]==v[n][m]){
            sol+=d[ua[k][n]][ub[k][m]];
            if(sol>=MOD)
                sol-=MOD;
        }
    fout<<sol<<"\n";
    return 0;
}