#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

string A, B;
int n, m;
int ls[503][503];
int counti[503][503];

int preva[27][503];
int prevb[27][503];

int main() {
    ifstream fin("subsir.in");
    ofstream fout("subsir.out");
    
    fin >> A >> B;
    
    n = A.size(); m = B.size();
    A = " " + A; B = " " + B;
    //dinamica pt subsir
    int i, j;
    for (i = 1; i <= n; ++i)
    for (j = 1; j <= m; ++j) {
        if (A[i] == B[j]) { ls[i][j] = ls[i-1][j-1] + 1; continue;}
        ls[i][j] = max(ls[i-1][j], ls[i][j-1]);
        }        
    for (i = 1; i <= n; ++i) for (int k = 0; k < 26; ++k) {
        preva[k][i] = preva[k][i-1];
        if (A[i-1] - 'a' == k) preva[k][i] = i - 1;        
        }
    for (i = 1; i <= m; ++i) for (int k = 0; k < 26; ++k) {
        prevb[k][i] = prevb[k][i-1];
        if (B[i-1] -'a' == k) prevb[k][i] = i - 1;
        }
    //count alea de lungime maximala
    for (i = 1; i <= n; ++i)
    for (j = 1; j <= m; ++j) if (A[i] == B[j]) {
        //find daca e multipla..
        int k;
        
        for (k = 0; k < 26; ++k) if (ls[i][j] == ls[preva[k][i]][prevb[k][j]] + 1)
        counti[i][j] += counti[preva[k][i]][prevb[k][j]], counti[i][j] %= 666013;
        counti[i][j] = max(1, counti[i][j]);
        }        
    int total = 0;
    for (i = 1; i <= n; ++i)
    for (j = 1; j <= m; ++j) if (A[i] == B[j] && ls[i][j] == ls[n][m]) {
        int k = 0;
        int ok = 0;
        for (k = i + 1; k <= n; ++k) if (A[k] == A[i]) {ok=1; break;}
        if (ok) continue;
        for (k = j + 1; k <= m; ++k) if (B[k] == B[j]) {ok = 1; break;}
        if (ok) continue;
        total = (total + counti[i][j])%666013;
            
        }
        
    fout << total << '\n';
    return 0;
    }