#include <fstream>
#include <cstring>
#define NM 510
#define x first
#define y second
#define MOD 666013

using namespace std;

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

char A[NM], B[NM];
int L[NM][NM], DP[NM][NM];
pair<int, int> W[27][NM][NM];
int N, M;
int i, j, k;

int main ()
{
    f >> (A+2);
    N=strlen(A+2);
    f >> (B+2);
    M=strlen(B+2);
    N++; M++;

    for (i=0; i<=N; i++)
        for (j=0; j<=M; j++)
            for (k=0; k<=26; k++)
                W[k][i][j]=make_pair(0, 0);

    W[0][1][1]=make_pair(1, 1);
    W[0][2][1]=W[0][1][1];
    W[0][1][2]=W[0][1][1];
    DP[1][1]=1;
    L[1][1]=1;
    L[1][2]=1;
    L[2][1]=1;

    for (i=2; i<=N; i++)
        for (j=2; j<=M; j++)
            if (A[i]==B[j])
            {
                L[i][j]=1+L[i-1][j-1];
                for (k=0; k<=26; k++)
                {
                    if (L[W[k][i-1][j-1].x][W[k][i-1][j-1].y]+1==L[i][j])
                        DP[i][j]+=DP[W[k][i-1][j-1].x][W[k][i-1][j-1].y];
                    if (DP[i][j]>=MOD)
                        DP[i][j]-=MOD;
                }

                for (k=0; k<=26; k++)
                {
                    int maxi=max(L[W[k][i-1][j-1].x][W[k][i-1][j-1].y], max(L[W[k][i][j-1].x][W[k][i][j-1].y], L[W[k][i-1][j].x][W[k][i-1][j].y]));

                    if (L[W[k][i-1][j-1].x][W[k][i-1][j-1].y]==maxi) W[k][i][j]=W[k][i-1][j-1];
                    if (L[W[k][i-1][j].x][W[k][i-1][j].y]==maxi) W[k][i][j]=W[k][i-1][j];
                    if (L[W[k][i][j-1].x][W[k][i][j-1].y]==maxi) W[k][i][j]=W[k][i][j-1];
                }

                k=A[i]-'a'+1;
                if (L[i][j]>L[W[k][i][j].x][W[k][i][j].y])
                    W[k][i][j]=make_pair(i, j);
            }
            else
            {
                L[i][j]=max(L[i-1][j], L[i][j-1]);

                for (k=0; k<=26; k++)
                {
                    int maxi=max(L[W[k][i-1][j-1].x][W[k][i-1][j-1].y], max(L[W[k][i][j-1].x][W[k][i][j-1].y], L[W[k][i-1][j].x][W[k][i-1][j].y]));

                    if (L[W[k][i-1][j-1].x][W[k][i-1][j-1].y]==maxi) W[k][i][j]=W[k][i-1][j-1];
                    if (L[W[k][i-1][j].x][W[k][i-1][j].y]==maxi) W[k][i][j]=W[k][i-1][j];
                    if (L[W[k][i][j-1].x][W[k][i][j-1].y]==maxi) W[k][i][j]=W[k][i][j-1];
                }
            }

    int ANS=0;
    for (k=0; k<=26; k++)
    {
        if (L[W[k][N][M].x][W[k][N][M].y]==L[N][M]) ANS+=DP[W[k][N][M].x][W[k][N][M].y];
        if (ANS>=MOD)
            ANS-=MOD;
    }

    g << ANS << '\n';

    f.close();
    g.close();

    return 0;
}