#include <cstdio>
#include <cstring>

using namespace std;

const int NMAX = 500;
const int MOD = 666013;

int N, M;
int d[1 + NMAX + 1][1 + NMAX + 1], sol[1 + NMAX + 1][1 + NMAX + 1];
char s1[1 + NMAX + 1], s2[1 + NMAX + 1];

int main(){
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);

    gets(s1 + 1);
    gets(s2 + 1);
    N = strlen(s1 + 1);
    M = strlen(s2 + 1);

    for (int i = 0; i <= N ; ++i)
        sol[i][0] = 1;
    for (int i = 0; i <= M; ++i)
        sol[0][i] = 1;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) {
            if (s1[i] == s2[j]) {
                d[i][j] = d[i - 1][j - 1] + 1;
                sol[i][j] = sol[i - 1][j - 1];
            }
            else if (d[i - 1][j] > d[i][j - 1]) {
                d[i][j] = d[i - 1][j];
                sol[i][j] = sol[i - 1][j];
            }
            else if (d[i - 1][j] < d[i][j - 1]) {
                d[i][j] = d[i][j - 1];
                sol[i][j] = sol[i][j - 1];
            }
            else {
                d[i][j] = d[i - 1][j];
                sol[i][j] = (sol[i - 1][j] + sol[i][j - 1]) % MOD;
                if (d[i - 1][j] == d[i - 1][j - 1])
                    sol[i][j] = (sol[i][j] - sol[i - 1][j - 1] + MOD) % MOD;
            }
        }

    printf("%d\n", sol[N][M]);

    return 0;
}