#include<fstream>
#include<cstring>

using namespace std;

#define NMAX 502
#define MOD 666013
#define alf 30

ifstream fin("subsir.in");
ofstream fout("subsir.out");

int N;int M; int C[NMAX][NMAX];int D[NMAX][NMAX]; int indA[NMAX][alf]; int indB[NMAX][alf];

char A[NMAX]; char B[NMAX];

void Read() {

    fin >> (A + 1)>> (B + 1);
    N = strlen(A + 1);
    M = strlen(B + 1);
    A[++N] = '#';
    B[++M] = '#';
}

void Solve() {

    for(int i = 1; i <= N; ++i){
        for(int j = 0; j < alf; ++j)
            indA[i][j] = indA[i - 1][j];
        indA[i][A[i] - 'a'] = i;
    }

    for(int i = 1; i <= N; ++i){
        for(int j = 0; j < alf; ++j)
            indB[i][j] = indB[i - 1][j];
        indB[i][B[i] - 'a'] = i;
    }
    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]);

    D[0][0] = 1;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; ++j){
            if(C[i][j] == 1){
                D[i][j] = 1;
                continue;
            }
            for(int k = 0 ;k < alf; ++k){
                int ii = indA[i - 1][k];
                int jj = indB[j - 1][k];
                if(C[i][j] == C[ii][jj] + 1)
                    D[i][j] += D[ii][jj], D[i][j] %= MOD;
            }
        }
    fout << D[N][M];
}


int main() {

    Read ();

    Solve ();

    return 0;
}