#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int NMAX = 501,
          MOD = 666013;

int C[NMAX+4][NMAX+4], nr[NMAX+4][NMAX+4];
char A[NMAX+4], B[NMAX+4];


void calc(int m, int n) {
    for(int i = 0; i <= m; i++)
        nr[i][0] = 1;
    for(int i = 0; i <= n; i++)
        nr[0][i] = 1;

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            if(A[i] == B[j]) {
                C[i][j] = C[i - 1][j - 1] + 1;
                nr[i][j] = nr[i-1][j-1];
            } else {
                C[i][j] = max(C[i-1][j], C[i][j-1]);

                if(C[i-1][j] == C[i][j-1]) {
                    nr[i][j] = (nr[i][j] + nr[i][j-1]) % MOD;
                    if(C[i-1][j] == C[i-1][j-1])
                        nr[i][j] = (nr[i][j] - nr[i-1][j-1] + MOD) % MOD;
                } else if(C[i-1][j] > C[i][j-1])
                    nr[i][j] += nr[i-1][j];
                else nr[i][j] = nr[i][j-1];
            }
}

int main() {
    in.getline(A+1, NMAX+1);
    in.getline(B+1, NMAX+1);

    int lg_1 = strlen(A+1),
        lg_2 = strlen(B+1);

    calc(lg_1, lg_2);

    out << nr[lg_1][lg_2];
    return 0;
}