#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

const int MAXL = 505;
const int MO = 666013;
string A, B;
int lungA, lungB;
int LCS[MAXL][MAXL];
int best[MAXL][MAXL];

void Read() {
    fin >> A >> B;
    lungA = A.size();
    lungB = B.size();
    A = "0" + A;
    B = "0" + B;
}

void Solve() {
    for (int i = 1; i <= lungA; ++i) {
        for (int j = 1; j <= lungB; ++j) {
            if (A[i] == B[j]) {//upper-left
                LCS[i][j] = 1 + LCS[i - 1][j - 1];
                best[i][j] = best[i - 1][j - 1];
                if (!best[i][j])
                    ++best[i][j];
            }else {
                if (LCS[i - 1][j] > LCS[i][j - 1]) {//we'd better take from up
                    LCS[i][j] = LCS[i - 1][j];
                    best[i][j] = best[i - 1][j];
                }else
                if (LCS[i - 1][j] < LCS[i][j - 1]) {//take from left
                    LCS[i][j] = LCS[i][j - 1];
                    best[i][j] = best[i][j - 1];
                }else {//equality
                    LCS[i][j] = LCS[i - 1][j];
                    best[i][j] = (((best[i][j] + best[i - 1][j]) % MO) + best[i][j - 1]) % MO;
                    if (LCS[i][j] == LCS[i - 1][j - 1])
                        best[i][j] = (best[i][j] - best[i - 1][j - 1] + MO) % MO;
                }
            }
        }
    }
}

void afis() {
    for (int i = 0; i <= lungA; ++i) {
        for (int j = 0; j <= lungB; ++j) {
            cerr << best[i][j] << ' ';
        }cerr << '\n';
    }
}

int main() {
    Read();
    Solve();
    afis();
    fout << best[lungA][lungB] << '\n';
    fin.close();
    fout.close();
    return 0;
}