#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 666013
#define nmax 505
 
using namespace std;
 
int pa[nmax][100], pb[nmax][100], c[nmax][nmax], nr[nmax][nmax], rez, n, m;
char a[nmax], b[nmax];
 
void citeste(){
 
    scanf("%s", a+1);
    scanf("%s", b+1);
    n = strlen(a+1);
    m = strlen(b+1);
 
}
 
void rezolva(){
 
    for(int i=1; i<=n; i++){
        pa[i][a[i]] = i;
        for(char ch='a'; ch<='z'; ++ch){
            if (ch == a[i]) continue;
            pa[i][ch] = pa[i-1][ch];
        }
    }
 
    for(int i=1; i<=m; i++){
        pb[i][b[i]] = i;
        for(char ch='a'; ch<='z'; ++ch){
            if (ch == b[i]) continue;
            pb[i][ch] = pb[i-1][ch];
        }
    }
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if (a[i] == b[j])
                c[i][j] = c[i-1][j-1] + 1;
            else c[i][j] = max(c[i-1][j], c[i][j-1]);
        }
    }
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if (a[i] != b[j]) continue;
            if (c[i][j] == 1){
                nr[i][j] = 1;
                continue;
            }
            for(char ch='a'; ch<='z'; ++ch){
                int ii = pa[i-1][ch];
                int jj = pb[j-1][ch];
                if (c[ii][jj] + 1 == c[i][j])
                    nr[i][j] += nr[ii][jj] % MOD;
            }
        }
    }
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if (nr[i][j] && c[i][j] == c[n][m]){
                if (pa[n][a[i]] == i && pb[m][a[i]] == j)
                    rez += nr[i][j] % MOD;
            }
        }
    }
 
}
 
void scrie(){
 
    printf("%d\n", rez);
 
}
 
int main(){
 
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
 
    citeste();
    rezolva();
    scrie();
 
    fclose(stdin);
    fclose(stdout);
 
    return 0;
 
}