#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, 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];
}

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;
}

// 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";

    sol = conv(recon(n1, n2));

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

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