#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
const string problem("subsir");
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
using VI = vector<int>;
using VVI = vector<VI>;
const int mod(666013);
string a, b;
int n, m;
VVI lmax, moduri;
inline void Adun(int& a, const int& b) {
    a += b;
    if (a >= mod)
        a -= mod;
}
inline void Scad(int& a, const int& b) {
    a -= b;
    if (a < 0)
        a += mod;
}
int main() {
    DAU
    fin >> a >> b;
    n = static_cast<int>(a.size());
    m = static_cast<int>(b.size());
    lmax = moduri = VVI(n + 1, VI(m + 1));
    a = '$' + a;
    b = '$' + b;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i] == b[j]) {
                lmax[i][j] = lmax[i-1][j-1] + 1;
                moduri[i][j] = max(1, moduri[i-1][j-1]);
            }
            else {
                lmax[i][j] = max(lmax[i-1][j], lmax[i][j-1]);
                if (lmax[i][j] == lmax[i-1][j])
                    Adun(moduri[i][j], moduri[i-1][j]);
                if (lmax[i][j] == lmax[i][j-1])
                    Adun(moduri[i][j], moduri[i][j-1]);
                if (lmax[i][j] == lmax[i-1][j-1])
                    Scad(moduri[i][j], moduri[i-1][j-1]);
            }
    fout << moduri[n][m];
    PLEC
}