#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
const int MAX_N = 512;
const int MOD = 666013;

int last_a[MAX_N][26];
int last_b[MAX_N][26];
int c[MAX_N][MAX_N];
int cnt[MAX_N][MAX_N];

int main() {
    ifstream fin("subsir.in");
    ofstream fout("subsir.out");
    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 < 26; ++ 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 < 26; ++ 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]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                for (int ch = 0; ch < 26; ++ ch) {
                    int ii = last_a[i - 1][ch];
                    int jj = last_b[j - 1][ch];
                    if (c[i][j] == c[ii][jj] + 1) {
                        cnt[i][j] += cnt[ii][jj];
                        if (cnt[i][j] >= MOD) {
                            cnt[i][j] -= MOD;
                        }
                    }
                }
                if (cnt[i][j] == 0) {
                    cnt[i][j] = 1;
                }
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
    }
    int answer = 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'] && c[i][j] == c[n][m]) {
                answer += cnt[i][j];
                if (answer >= MOD) {
                    answer -= MOD;
                }
            }
        }
    }
    fout << answer << "\n";
    return 0;
}