#include <iostream>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <algorithm>
using namespace std;

constexpr int sigma = 26;
constexpr int mod = 666013;

void mk_nexts(const string& str, vector<array<int, sigma>>& next){
    fill(begin(next.back()), end(next.back()), -1);

    for(int i = str.size()-1; i >= 0; --i){
        copy(begin(next[i+1]), end(next[i+1]), begin(next[i]));
        next[i][str[i]-'a'] = i+1;
    }
}

void norm(int& x){
    if(x >= mod){
        x -= mod;
    }
}

int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    string s1, s2;
    f >> s1 >> s2;

    const int n = s1.size(), m = s2.size();
    vector<array<int, sigma>> next1(n+1), next2(m+1);
    mk_nexts(s1, next1);
    mk_nexts(s2, next2);

    vector<vector<int>> best(n+1, vector<int>(m+1, 0)), cnt(n+1, vector<int>(m+1, 0));
    best[0][0] = 1;
    cnt[0][0] = 1;
    int best_fin = 0, rez_fin = 0;
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            if(best_fin < best[i][j]){
                best_fin = best[i][j];
                rez_fin = cnt[i][j];
                norm(rez_fin);
            }
            else if(best_fin == best[i][j]){
                rez_fin += cnt[i][j];
                norm(rez_fin);
            }
            for(int ch = 0; ch < sigma; ++ch){
                const int ni = next1[i][ch], nj = next2[j][ch];
                if(ni == -1 || nj == -1){
                    continue;
                }
                if(best[ni][nj] < best[i][j]+1){
                    best[ni][nj] = best[i][j]+1;
                    cnt[ni][nj] = cnt[i][j];
                    norm(cnt[ni][nj]);
                }
                else if(best[ni][nj] == best[i][j]+1){
                    cnt[ni][nj] += cnt[i][j];
                    norm(cnt[ni][nj]);
                }
            }
        }
    }
    g << rez_fin;

    return 0;
}