#include <stdio.h>
#include <string.h>

#define MAXN 505
#define ALPHA 26
#define MOD 666013

static char s[MAXN], t[MAXN];
static int n, m;
static int lcs[MAXN][MAXN];
static int nextS[MAXN][ALPHA];
static int nextT[MAXN][ALPHA];
static int memo[MAXN][MAXN];

static int count_lcs(int i, int j) {
    if (lcs[i][j] == 0) return 1;
    if (memo[i][j] != -1) return memo[i][j];

    int ans = 0;
    for (int c = 0; c < ALPHA; ++c) {
        int i1 = nextS[i][c];
        int j1 = nextT[j][c];
        if (i1 < n && j1 < m && lcs[i1 + 1][j1 + 1] == lcs[i][j] - 1) {
            ans += count_lcs(i1 + 1, j1 + 1);
            if (ans >= MOD) ans %= MOD;
        }
    }

    memo[i][j] = ans % MOD;
    return memo[i][j];
}

int main(void) {
    FILE *fin = fopen("subsir.in", "r");
    FILE *fout = fopen("subsir.out", "w");
    if (!fin || !fout) return 0;

    if (fscanf(fin, "%500s", s) != 1) {
        return 0;
    }
    if (fscanf(fin, "%500s", t) != 1) {
        return 0;
    }

    n = (int)strlen(s);
    m = (int)strlen(t);

    for (int c = 0; c < ALPHA; ++c) {
        nextS[n][c] = n;
        nextT[m][c] = m;
    }
    for (int i = n - 1; i >= 0; --i) {
        for (int c = 0; c < ALPHA; ++c) nextS[i][c] = nextS[i + 1][c];
        nextS[i][s[i] - 'a'] = i;
    }
    for (int j = m - 1; j >= 0; --j) {
        for (int c = 0; c < ALPHA; ++c) nextT[j][c] = nextT[j + 1][c];
        nextT[j][t[j] - 'a'] = j;
    }

    for (int i = n; i >= 0; --i) {
        for (int j = m; j >= 0; --j) {
            if (i == n || j == m) {
                lcs[i][j] = 0;
            } else if (s[i] == t[j]) {
                lcs[i][j] = lcs[i + 1][j + 1] + 1;
            } else {
                int a = lcs[i + 1][j];
                int b = lcs[i][j + 1];
                lcs[i][j] = (a > b) ? a : b;
            }
        }
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            memo[i][j] = -1;
        }
    }

    int result = count_lcs(0, 0) % MOD;
    fprintf(fout, "%d\n", result);

    fclose(fin);
    fclose(fout);
    return 0;
}