#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(Sol[i-1][j]==Sol[i-1][j-1])///scad numarul sirurilor identice
                        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 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;
}