#include <fstream>
#include <cstring>
#define NM 505
#define MOD 666013

using namespace std;

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

char a[NM], b[NM];
long long x, y, i, j, M[NM][NM], F[NM][NM], val;
bool D[NM][NM];

int main()
{
    fin.getline(a, NM);
    fin.getline(b, NM);
    x=strlen(a)-1;
    y=strlen(b)-1;
    for (i=y; i>=0; i--)
    {
        for (j=x; j>=0; j--)
        {
            M[i][j]=max(M[i+1][j], M[i][j+1]);
            if (a[j]==b[i])
            {
                M[i][j]=M[i+1][j+1]+1;
                D[i][j]=1;
            }
        }
    }
    for (i=y; i>=0; i--)
    {
        for (j=x; j>=0; j--)
        {
            val=M[i][j];
            if (D[i][j])
            {
                if (F[i+1][j+1]==0)
                    F[i][j]=1;
                else
                    F[i][j]=F[i+1][j+1];
                continue;
            }
            if (M[i+1][j]==val)
            {
                F[i][j]+=F[i+1][j];
                F[i][j]%=MOD;
            }
            if (M[i][j+1]==val)
            {
                F[i][j]+=F[i][j+1];
                F[i][j]%=MOD;
            }
            if (M[i+1][j+1]==val)
            {
                F[i][j]-=F[i+1][j+1];
                //F[i][j]+=MOD;
                F[i][j]%=MOD;
            }
            F[i][j]%=MOD;
        }
    }
    fout<<F[0][0]%MOD;
    return 0;
}