#include <cstdio>
#include <cstring>
#define nmax 510
#define mod 666013
using namespace std;

char a[nmax], b[nmax];
int lgA,lgB,i,j, M[nmax][nmax], nr[nmax][nmax];;

int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
    scanf("%s%s", a+1, b+1);

    lgA=strlen(a+1);
    lgB=strlen(b+1);

    for(i=1;i<=lgA;++i)
        for(j=1;j<=lgB;++j)
        {
            if(a[i]==b[j])
            {
                M[i][j]=M[i-1][j-1]+1;
                if(M[i][j]==1)
                    nr[i][j]=1;
                else
                    nr[i][j]=nr[i-1][j-1];
            }
            else
            {
                if(M[i-1][j]<M[i][j-1])
                {
                    M[i][j]=M[i][j-1];
                    nr[i][j]=nr[i][j-1];
                }
                else
                    if(M[i-1][j]>M[i][j-1])
                    {
                        M[i][j]=M[i-1][j];
                        nr[i][j]=nr[i-1][j];
                    }
                    else
                    {
                        M[i][j]=M[i][j-1];
                        nr[i][j]=(nr[i-1][j]+nr[i][j-1])%mod;
                        if(M[i-1][j-1]==M[i-1][j])
                            nr[i][j]=(nr[i][j]-nr[i-1][j-1])%mod;
                    }

            }
        }

    /*for(i=1;i<=lgA;++i)
    {
        for(j=1;j<=lgB;++j)
            printf("%d ", M[i][j]);
        printf("\n");
    }
    printf("\n");
    for(i=1;i<=lgA;++i)
    {
        for(j=1;j<=lgB;++j)
            printf("%d ", nr[i][j]);
        printf("\n");
    }*/

    printf("%d", nr[lgA][lgB]);

    return 0;
}