#include <bits/stdc++.h>

using namespace std;
const int kMod = 666013;

void combine(pair<int, int>& a, pair<int, int> b) {
    if (b.first < a.first) return;
    if (b.first > a.first) {
        a = b; return;
    }
    a.second += b.second;
    while (a.second >= kMod) 
        a.second -= kMod;
}

int main() {
    ifstream cin("subsir.in");
    ofstream cout("subsir.out");

    string s, t; cin >> s >> t;
    int n = s.size(), m = t.size();

    pair<int, int> ans = {-1e9, 0};
    vector<int> ns(26, n), nt;
    
    vector<vector<pair<int, int>>> dp(n + 1, 
            vector<pair<int, int>>(m + 1, ans));
    for (int i = n - 1; i >= 0; --i) {
        nt.assign(26, m);
        for (int j = m - 1; j >= 0; --j) {
            if (s[i] == t[j]) {
                dp[i][j] = {1, 1}; 
                for (int c = 0; c < 26; ++c) {
                    int ip = ns[c], jp = nt[c];
                    auto p = dp[ip][jp]; p.first += 1;
                    combine(dp[i][j], p); 
                }
            }
            nt[t[j] - 'a'] = j;
        }
        ns[s[i] - 'a'] = i;
    }
    for (int i = 0; i < 26; ++i)
        combine(ans, dp[ns[i]][nt[i]]);
    cout << ans.second << endl;

    return 0;
}