#include <bits/stdc++.h>

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

#define MAXN   505
#define MOD 666013

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

void Dynamic() {
    for (int i=0; i<=N; ++i)
        Count[i][0] = 1;
    for (int i=0; i<=M; ++i)
        Count[0][i] = 1;

    for (int i=1, j; i<=N; ++i)
        for (j=1; j<=M; ++j) {
            if (A[i] == B[j])
                DP[i][j] = DP[i-1][j-1] + 1,
                Count[i][j] = Count[i-1][j-1];
            else if (DP[i-1][j] > DP[i][j-1])
                DP[i][j] = DP[i-1][j],
                Count[i][j] = Count[i-1][j];
            else if (DP[i][j-1] > DP[i-1][j])
                DP[i][j] = DP[i][j-1],
                Count[i][j] = Count[i][j-1];
            else {
                DP[i][j] = DP[i-1][j];
                Count[i][j] = (Count[i-1][j] + Count[i][j-1]) % MOD;
                if (DP[i-1][j-1] == DP[i-1][j])
                    Count[i][j] = (Count[i][j] - Count[i-1][j-1] + MOD) % MOD;
            }
        }
}

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() {
    Dynamic();
    Out << Count[N][M] << '\n';
}

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

    return 0;
}