#include <cstdio>
#define MOD 666013
#define MAXN 500
char a[MAXN+1], b[MAXN+1];
int l[MAXN+1][MAXN+1], d[MAXN+1][MAXN+1], last[MAXN+1][26], ult[MAXN+1][26];
int main(){
    int n, m, i, j, c, ans;
    char ch;
    FILE *fin, *fout;
    fin=fopen("subsir.in", "r");
    fout=fopen("subsir.out", "w");
    ch=fgetc(fin);
    n=0;
    while(ch!='\n'){
        a[++n]=ch-'a';
        for(i=0; i<26; i++){
            last[n][i]=last[n-1][i];
        }
        last[n][(int)a[n]]=n;
        ch=fgetc(fin);
    }
    ch=fgetc(fin);
    m=0;
    while(ch!='\n'){
        b[++m]=ch-'a';
        for(i=0; i<26; i++){
            ult[m][i]=ult[m-1][i];
        }
        ult[m][(int)b[m]]=m;
        ch=fgetc(fin);
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            if(a[i]==b[j]){
                l[i][j]=1+l[i-1][j-1];
                if(l[i][j]==1){
                    d[i][j]=1;
                }else{
                    for(c=0; c<26; c++){
                        if(l[i][j]==1+l[last[i-1][c]][ult[j-1][c]]){
                            d[i][j]+=d[last[i-1][c]][ult[j-1][c]];
                        }
                    }
                    d[i][j]%=MOD;
                }
            }
            if(l[i][j]<l[i-1][j]){
                l[i][j]=l[i-1][j];
            }
            if(l[i][j]<l[i][j-1]){
                l[i][j]=l[i][j-1];
            }
        }
    }
    ans=0;
    for(i=0; i<26; i++){
        if(l[last[n][i]][ult[m][i]]==l[n][m]){
            ans+=d[last[n][i]][ult[m][i]];
        }
    }
    ans%=MOD;
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}