#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], sol[N][N], n1, n2;
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 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] - 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";

    // reconstruct all distinct lcs
    //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] % MOD);
    return 0;
}