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

#define Nmax 505
char a[Nmax], b[Nmax];
int best[Nmax][Nmax], number[Nmax][Nmax];
int n, m;
const int MOD = 666013;

void read()
{
    freopen("subsir.in", "r", stdin);

    fgets(a + 1, Nmax, stdin);
    fgets(b + 1, Nmax, stdin);

    n = strlen(a + 1);
    m = strlen(b + 1);
    --n;
    --m;

    fclose(stdin);
}

void solve()
{
    for (int i = 0; i <= n; ++i)
        number[i][0] = 1;
    for (int i = 0; i <= m; ++i)
        number[0][i] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j){
            if (a[i] == b[j]){
                best[i][j] = best[i - 1][j - 1] + 1;
                number[i][j] = number[i - 1][j - 1];
            } else{
                if (best[i - 1][j] > best[i][j - 1]){
                    best[i][j] = best[i - 1][j];
                    number[i][j] = number[i - 1][j];
                } else if (best[i][j - 1] > best[i - 1][j]){
                    best[i][j] = best[i][j - 1];
                    number[i][j] = number[i][j - 1];
                } else{
                    best[i][j] = best[i - 1][j];
                    number[i][j] = (number[i - 1][j] + number[i][j - 1]) % MOD;
                    if (best[i][j] == best[i - 1][j - 1])
                        number[i][j] = (number[i][j] - number[i - 1][j - 1] + MOD) % MOD;
                }
            }
        }
}

void write()
{
    freopen("subsir.out", "w", stdout);

    printf("%d\n", number[n][m]);

    fclose(stdout);
}

int main()
{
    read();
    solve();
    write();
}