#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;
string A, B;
int N, M;
int L[505][505];
int dp[505][505];
int nxt_A[505][26];
int nxt_B[505][26];

int solve(int i, int j) {
    if (i > 0 && j > 0 && L[i][j] == 1) return 1;
    if (dp[i][j] != -1) return dp[i][j];

    int ans = 0;
    int target = (i == 0 && j == 0) ? L[0][0] : L[i][j] - 1;

    for (int c = 0; c < 26; ++c) {
        int p = nxt_A[i][c];
        int q = nxt_B[j][c];
        if (p <= N && q <= M) {
            if (L[p][q] == target) {
                ans = (ans + solve(p, q)) % MOD;
            }
        }
    }
    return dp[i][j] = ans;
}

int main() {
    fin >> A >> B;
    N = A.length();
    M = B.length();

    for (int i = N; i >= 1; --i) {
        for (int j = M; j >= 1; --j) {
            if (A[i - 1] == B[j - 1]) {
                L[i][j] = 1 + L[i + 1][j + 1];
            } else {
                L[i][j] = max(L[i + 1][j], L[i][j + 1]);
            }
        }
    }
    L[0][0] = L[1][1];

    for (int c = 0; c < 26; ++c) nxt_A[N][c] = N + 1;
    for (int i = N - 1; i >= 0; --i) {
        for (int c = 0; c < 26; ++c) {
            nxt_A[i][c] = nxt_A[i + 1][c];
        }
        nxt_A[i][A[i] - 'a'] = i + 1;
    }

    for (int c = 0; c < 26; ++c) nxt_B[M][c] = M + 1;
    for (int j = M - 1; j >= 0; --j) {
        for (int c = 0; c < 26; ++c) {
            nxt_B[j][c] = nxt_B[j + 1][c];
        }
        nxt_B[j][B[j] - 'a'] = j + 1;
    }

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            dp[i][j] = -1;
        }
    }

    if (L[0][0] == 0) {
        fout << 0 << "\n";
    } else {
        fout << solve(0, 0) << "\n";
    }

    return 0;
}