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

ifstream fin("subsir.in");
ofstream fout("subsir.out");

const int MAXL = 505;
const int modo = 666013;
string A, B;
int lungA, lungB;
int d[MAXL][MAXL];
int best[MAXL][MAXL];
int i,j;

int main() {
    fin >> A >> B;
    lungA = A.size();
    lungB = B.size();
    A = "0" + A;
    B = "0" + B;
    for(i=1;i<=lungA;i++)
    {
        for(j=1;j<=lungB;j++)
        {
            if(A[i]==B[j])
            {
                d[i][j]=d[i-1][j-1]+1;
                best[i][j]=best[i-1][j-1];
                if(best[i][j]==0)
                {
                    best[i][j]=1;
                }
            }
            else
            {
                if(d[i][j-1]>d[i-1][j])
                {
                    d[i][j]=d[i][j-1];
                    best[i][j]=best[i][j-1];
                }
                else
                {
                    if(d[i][j-1]<d[i-1][j])
                    {
                        d[i][j]=d[i-1][j];
                        best[i][j]=best[i-1][j];
                    }

                    else
                    {
                        if(d[i][j-1]==d[i][j-1])
                        {
                            d[i][j]=d[i][j-1];
                            best[i][j] = (((best[i][j] + best[i - 1][j]) % modo) + best[i][j - 1]) % modo;
                           // best[i][j]=((best[i][j]- best[i-1][j-1])+modo)%modo;
                        }
                    }
                }
            }

        }
    }

    for(i=1;i<=lungA;i++)
    {
        for(j=1;j<=lungB;j++)
        {
            //fout<<best[i][j]<<" ";
        }
       // fout<<"\n";
    }
    fout<<best[lungA][lungB]%modo;
}