#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

#define Nmax 512
#define modulo 666013

char A[Nmax], B[Nmax];
int D[Nmax][Nmax], S[Nmax][Nmax];

int N, M;

void citire(){

    ifstream f("subsir.out");

    f >> A >> B;

    N = strlen( A );
    M = strlen( B );

    f.close();
}

void init(){

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

    for ( int i = 0; i <= M; i++ )
            S[0][i] = 1;
}

void rezolva(){

    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],
                S[i][j] = S[i - 1][j - 1];
            else
                if ( D[i - 1][j] == D[i][j - 1] ){

                    D[i][j] = D[i - 1][j];
                    S[i][j] = ( S[i - 1][j] + S[i][j - 1] ) % modulo;

                    if ( D[i - 1][j - 1] == D[i][j - 1] )
                        S[i][j] = ( S[i][j] - S[i - 1][j - 1] + modulo ) % modulo;
                }
                else
                    if ( D[i - 1][j] > D[i][j - 1] )
                        D[i][j] = D[i - 1][j],
                        S[i][j] = S[i - 1][j];
                    else
                        D[i][j] = D[i][j - 1],
                        S[i][j] = S[i][j - 1];
}

void afis(){

    ofstream g("subsir.out");

    g << S[N][M] << "\n";

    g.close();
}

int main(){

    citire();
    init();
    rezolva();
    afis();

    return 0;
}