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

#define N 501

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

int dp[N][N], n1, n2, lcslen;
string s1, s2;
unordered_set<string> sol;

int find() {
    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]);

    return dp[n1][n2];
}

void recon(int i, int j) {

    int idx = lcslen;
    char lcs[N];
    lcs[idx] = '\0';

    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs[--idx] = s1[i - 1];
            i--;
            j--;
        } else {
            if (dp[i - 1][j] > dp[i][j - 1])
                i--;
            else 
                j--;
        }
    }

    sol.insert(lcs);
}

// void find(int k1, int k2, int maxFound) {
//     for (int i = k1; i < n1; i++) {
//         for (int j = k2; j < n2; j++) {
//             if (s[i] == ss[j]) {
//                 maxFound++;
//                 pd[i] = max(pd[i], maxFound);
//                 find(i + 1, j + 1, maxFound);
//                 maxFound = 0;
//                 for (int i = 1; i < n1; i++)
//                     cout << pd[i] << " ";
//                 cout << "\n";
//             }
//         }
//     }
// }

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

    lcslen = find();
    // cout << "lcslen: " << lcslen << "\n";

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

    for (int i = n1; i > 0; i--)
        for (int j = n2; j > 0; j--)
            if (dp[i][j] == lcslen)
                recon(i, j);

    // for(string lcs : sol)
    //     cout << lcs <<"\n";

    g << (sol.size() % 666013);
    return 0;
}