// Numarul de subsiruri comune maximale - top-down - Xp
#include <iostream>
#include <fstream>

int constexpr MAXN = 501;
int constexpr MOD = 666013;

std::string firstString, secondString;
int cache[MAXN][MAXN], ways[MAXN][MAXN];
bool isCached[MAXN][MAXN];

int dp(int i, int j) {
    if (i < 0 || j < 0) return 0;

    if (isCached[i][j]) {
        return cache[i][j];
    }

    if (firstString[i] == secondString[j]) {
        cache[i][j] = dp(i - 1, j - 1) + 1;
        ways[i][j] ++;
    } else {
        int columnDp = dp(i, j - 1);
        int rowDp = dp(i - 1, j);

        if (columnDp == rowDp) {
            ways[i][j] = ways[i][j - 1] + ways[i - 1][j];
            cache[i][j] = columnDp;
        } else {
            if (columnDp > rowDp) {
                cache[i][j] = columnDp;
                ways[i][j] = ways[i][j - 1];
            } else {
                cache[i][j] = rowDp;
                ways[i][j] = ways[i - 1][j];
            }
        }
    }

    ways[i][j] %= MOD;
    isCached[i][j] = true;
    return cache[i][j];
}

int main() {
    std::ifstream in("subsir.in");
    std::ofstream out("subsir.out");

    in >> firstString >> secondString;

    int lenFirst, lenSecond;
    lenFirst = firstString.size();
    lenSecond = secondString.size();

    int maxLength =  dp(lenFirst - 1, lenSecond - 1);
    out << ways[lenFirst - 1][lenSecond - 1] << "\n";
    return 0;
}