#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

const int NMax = 505;
const int Sigma = 26;
const int MOD = 666013;

int last_a[NMax][Sigma], last_b[NMax][Sigma];
int D[NMax][NMax], cnt[NMax][NMax];

int main(){
    int n, m;
    string a, b;
    fin >> a >> b;
    n = a.size();
    m = b.size();
    a = " " + a;
    b = " " + b;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < Sigma; j++){
            last_a[i][j] = last_a[i - 1][j];
        }
        last_a[i][a[i] - 'a'] = i;
    }
    for(int i = 1; i <= m; i++){
        for(int j = 0; j < Sigma; j++){
            last_b[i][j] = last_b[i - 1][j];
        }
        last_b[i][b[i] - 'a'] = i;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i] == b[j]){
                D[i][j] = D[i - 1][j - 1] + 1;
                for(int ch = 0; ch < Sigma; ch++){
                    int ii = last_a[i - 1][ch];
                    int jj = last_b[j - 1][ch];
                    if(D[i][j] == D[ii][jj] + 1){
                        cnt[i][j] += cnt[ii][jj];
                        cnt[i][j] %= MOD;
                    }
                }
                if(cnt[i][j] == 0){
                    cnt[i][j] = 1;
                }
            } else {
                D[i][j] = max(D[i - 1][j], D[i][j - 1]);
            }
        }
    }
    int sol = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == last_a[n][a[i] - 'a'] && j == last_b[m][b[j] - 'a'] && D[i][j] == D[n][m]){
                sol += cnt[i][j];
                sol %= MOD;
            }
        }
    }
    fout << sol;
    return 0;
}