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

int na, nb;
char a[501], b[501];
int dp[501][501], nr[501][501];

const int MOD = 666013;

void read() {
    ifstream f("subsir.in");
    f >> a >> b;
    f.close();
}

void solve() {
    int i, j;
    na = strlen(a), nb = strlen(b);
    for (i = 0; i <= na; i++)
        nr[i][0] = 1;
    for (i = 0; i <= nb; i++)
        nr[0][i] = 1;
    for (i = 1; i <= na; i++)
        for (j = 1; j <= nb; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                nr[i][j] = nr[i - 1][j - 1];
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (dp[i - 1][j] == dp[i][j - 1]) {
                    nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % MOD;
                    if (dp[i - 1][j] == dp[i - 1][j - 1])
                        nr[i][j] = (nr[i][j] - nr[i - 1][j - 1] + MOD) % MOD;
                }
                else 
                    if (dp[i - 1][j] > dp[i][j - 1])
                        nr[i][j] = nr[i - 1][j];
                    else nr[i][j] = nr[i][j - 1];
            }
        }
}

void output() {
    ofstream g("subsir.out");
    g << nr[na][nb];
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}