#include <bits/stdc++.h>
using namespace std;

#define N 501
#define MOD 666013

ifstream f("subsir.in");
ofstream g("subsir.out");

int dp[N][N], n1, n2;
unsigned long long sol[N][N];
string s1, s2;

void findlcs() {
    for (int i = 1; i < n1 + 1; i++)
        for (int j = 1; j < n2 + 1; j++)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else 
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

// void builds1() {
//     int dps1[N][26];
//     // for (int i = 0; i < 26; i++)
//     //      dps1[n1][i] = n1;
//     for (int i = n1; i >= 0; i--)
//         for (int j = 0; j < 26; j++)
//             dps1[i][j] = -1;

//     for (int i = n1 - 1; i >= 0; i--)
//         for (int j = 0; j < 26; j++)
//             if(s1[i] == 'a' + j)
//                 dps1[i][j] = i;
//             else
//                 dps1[i][j] = dps1[i + 1][j];

// }

void countlcs() {
    // lcs of 2 distinct strings is "" so has count 1
    for (int i = 0; i < n1 + 1; i++)
        sol[i][0] = 1;
    for (int j = 1; j < n2 + 1; j++)
        sol[0][j] = 1;

    for (int i = 1; i < n1 + 1; i++)
        for (int j = 1; j < n2 + 1; j++) {
            if (s1[i - 1] == s2[j - 1])
                sol[i][j] = sol[i - 1][j - 1];
            else {
                if (dp[i][j] == dp[i - 1][j]) {
                    sol[i][j] += sol[i - 1][j];
                    sol[i][j] %= MOD;
                }
                if (dp[i][j] == dp[i][j - 1]) {
                    sol[i][j] += sol[i][j - 1];
                    sol[i][j] %= MOD;
                }
                if (dp[i][j] == dp[i - 1][j - 1])
                    sol[i][j] -= sol[i - 1][j - 1];
            }
            sol[i][j] %= MOD;
        }
}

vector<string> recon(int i, int j) {
    if (i == 0 || j == 0)
        return {""};

    if (s1[i - 1] == s2[j - 1]) {
        vector<string> v = recon(i - 1, j - 1);
        for (string &s : v)
            s.push_back(s1[i - 1]);
        return v;   
    }

    if (dp[i - 1][j] > dp[i][j - 1])
        return recon(i - 1, j);
    if (dp[i - 1][j] < dp[i][j - 1])
        return recon(i, j - 1);

    vector<string> lt = recon(i - 1, j);
    vector<string> rt = recon(i, j - 1);
    lt.insert(lt.end(), rt.begin(), rt.end());

    return lt;
}

unordered_set<string> conv(vector<string> v) {
    unordered_set<string> s(v.begin(), v.end());
    return s;
}

int main() {
    f >> s1;
    f >> s2;
    n1 = s1.length();
    n2 = s2.length();

    findlcs();

    // for (int i = 1; i < n1 + 1; i++) {
    //     for (int j = 1; j < n2 + 1; j++)
    //         cout << dp[i][j] << " ";
    //     cout << "\n";
    // }
    // cout << "\n";

    countlcs();

    // for (int i = 1; i < n1 + 1; i++) {
    //     for (int j = 1; j < n2 + 1; j++)
    //         cout << sol[i][j] << " ";
    //     cout << "\n";
    // }
    // cout << "\n";

    //unordered_set<string> sols = conv(recon(n1, n2));
    //cout << "lcslen: " << dp[n1][n2] << "\n";
    // for (string s : sols)
    //     cout << s << "\n";
    //cout << (sol[n1][n2] % MOD);

    g << sol[n1][n2];
    return 0;
}