#include <fstream>
#include <cstring>
using namespace std;

ifstream f("subsir.in");
ofstream g("subsir.out");

const int NMAX = 501,
          MOD = 666013;

int N, M;
char A[NMAX], B[NMAX];
int D[NMAX][NMAX], Sol[NMAX][NMAX];

void dinamica()
{
    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(A[i - 1] == B[j - 1])
            {
                D[i][j] = D[i - 1][j - 1] + 1;
                Sol[i][j] = Sol[i - 1][j - 1];
            }
            else
            {
                D[i][j] = max(D[i - 1][j], D[i][j - 1]);
                if(D[i - 1][j] == D[i][j - 1])
                {
                    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;
                }
                else if(D[i - 1][j] > D[i][j - 1])
                    Sol[i][j] = Sol[i - 1][j];
                else if(D[i][j - 1] > D[i - 1][j])
                    Sol[i][j] = Sol[i][j - 1];
            }
}

int main()
{
    f.getline(A, NMAX);
    f.getline(B, NMAX);
    N = strlen(A);
    M = strlen(B);
    dinamica();
    g << Sol[N][M] << '\n';
    return 0;
}