#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>

#define MOD 666013
#define NMAX 505

using namespace std;

int lcs[NMAX][NMAX];
int dp[NMAX][NMAX];
string a, b;

void solve() {
    int m, n;

    m = a.length();
    n = b.length();

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == 1 || j == 1) {
                lcs[i][j] = 1;
                continue;
            }

            if (a[i - 1] == b[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1];
            } else {
                if (dp[i][j] == dp[i - 1][j]) {
                    lcs[i][j] = (lcs[i][j] + lcs[i - 1][j]) % MOD;
                }
                if (dp[i][j] == dp[i][j - 1]) {
                    lcs[i][j] = (lcs[i][j] + lcs[i][j - 1]) % MOD;
                }
                if (dp[i][j] == dp[i - 1][j - 1]) {
                    lcs[i][j] = (lcs[i][j] + MOD - lcs[i - 1][j - 1]) % MOD;
                }
            }
        }
    }

    cout << lcs[m][n];
}

int main() {
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);

    cin >> a >> b;
    solve();
}