#include<fstream>
#include<cstring>
#define mod 666013
using namespace std;
int n, m, i, j, k, ii, jj, rez;
char a[505], b[505];
int d[505][505], e[505][30], f[505][30], nr[505][505];
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int main(){
    fin>> a + 1;
    n = strlen(a + 1);
    fin>> b + 1;
    m = strlen(b + 1);
    for(i = 1; i <= n; i++){
        for(j = 0; j < 26; j++){
            if(a[i - 1] == j + 'a'){
                e[i][j] = i - 1;
            }
            else{
                e[i][j] = e[i - 1][j];
            }
        }
    }
    for(i = 1; i <= m; i++){
        for(j = 0; j < 26; j++){
            if(b[i - 1] == j + 'a'){
                f[i][j] = i - 1;
            }
            else{
                f[i][j] = f[i - 1][j];
            }
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(a[i] == b[j]){
                d[i][j] = d[i - 1][j - 1] + 1;
                if(d[i][j] == 1){
                    nr[i][j] = 1;
                    continue;
                }
                for(k = 0; k < 26; k++){
                    ii = e[i][k];
                    jj = f[j][k];
                    if(ii > 0 && jj > 0 && d[i][j] == 1 + d[ii][jj]){
                        nr[i][j] = (nr[ii][jj] + nr[i][j]) % mod;
                    }
                }
            }
            else{
                d[i][j] = max(d[i][j - 1], d[i - 1][j]);
            }
        }
    }
    if(a[n] == b[m]){
        rez = nr[n][m];
    }
    else{
        for(k = 0; k < 26; k++){
            ii = e[n][k];
            jj = f[m][k];
            if(ii > 0 && jj > 0 && d[n][m] == d[ii][jj]){
                rez = (nr[ii][jj] + rez) % mod;
            }
        }
    }
    fout<< rez <<"\n";
    return 0;
}