#include <bits/stdc++.h>

#define ALPHA ('z'-'a') + 1

#define MAXN   505
#define MOD 666013

int N, M, TrackA[MAXN][ALPHA], TrackB[MAXN][ALPHA];
char A[MAXN], B[MAXN];
int DP[MAXN][MAXN], Count[MAXN][MAXN];

void Precompute() {
    for (int i=1, j; i<=N; ++i) {
        for (j=0; j<ALPHA; ++j)
            TrackA[i][j] = TrackA[i-1][j],
            TrackB[i][j] = TrackB[i-1][j];
        TrackA[i][A[i]-'a'] = i;
        TrackB[i][B[i]-'a'] = i;
    }
}

int Ans, Best;
void Dynamic() {
    for (int i=1, j, k, l; i<=N; ++i)
        for (j=1; j<=M; ++j) {
            if (A[i] == B[j]) {
                DP[i][j] = DP[i-1][j-1] + 1;

                for (k=0; k<ALPHA; ++k)
                    for (l=0; l<ALPHA; ++l)
                        if (TrackA[i][k] && TrackB[j][l] && DP[TrackA[i][k]][TrackB[j][l]] + 1 == DP[i][j])
                            Count[i][j] = (Count[i][j] + Count[TrackA[i][k]][TrackB[j][l]]) % MOD;

                if (Count[i][j] == 0) Count[i][j] = 1;

                if (DP[i][j] > Best)
                    Best = DP[i][j], Ans = Count[i][j];
                else if (DP[i][j] == Best)
                    Ans += Count[i][j], Ans %= MOD;
           }
            else
                DP[i][j] = std::max(DP[i-1][j], DP[i][j-1]);
        }
}

std::ifstream In ("subsir.in");
std::ofstream Out("subsir.out");

void Citire() {
    In >> (A+1) >> (B+1);
    N = strlen(A+1);
    M = strlen(B+1);
}

void Rezolvare() {
    Precompute();
    Dynamic();
    Out << Ans << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}