#include <algorithm>
#include <string.h>
using namespace std;

#define MOD 666013
#define SIGMA 26
#define DIM 505

int ua[SIGMA][DIM],ub[SIGMA][DIM];
int c[DIM][DIM],nr[DIM][DIM];
char a[DIM],b[DIM];
int n,m,nrt;

void read ()
{
    fgets (a+1,DIM,stdin);
    a[0]=' ';
    n=strlen (a)-2;
    fgets (b+1,DIM,stdin);
    b[0]=' ';
    m=strlen (b)-2;
}

void solve ()
{
    int i,ii,j,jj,k;

    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
        {
            if (a[i]==b[j])
                c[i][j]=c[i-1][j-1]+1;
            else
                c[i][j]=max (c[i-1][j],c[i][j-1]);
            if (c[i][j]==1 && a[i]==b[j])
                nr[i][j]=1;
        }
    for (i=1; i<=n; ++i)
        for (j='a'; j<='z'; ++j)
            if (a[i]==j)
                ua[j-'a'][i]=i;
            else
                ua[j-'a'][i]=ua[j-'a'][i-1];
    for (i=1; i<=m; ++i)
        for (j='a'; j<='z'; ++j)
            if (b[i]==j)
                ub[j-'a'][i]=i;
            else
                ub[j-'a'][i]=ub[j-'a'][i-1];
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            if (a[i]==b[j])
            {
                for (k='a'; k<='z'; ++k)
                {
                    ii=ua[k-'a'][i-1];
                    jj=ub[k-'a'][j-1];
                    if (c[ii][jj]+1==c[i][j])
                        nr[i][j]=(nr[i][j]+nr[ii][jj])%MOD;
                }
                if (c[i][j]==c[n][m] && ua[a[i]-'a'][n]==i && ub[b[j]-'a'][m]==j)
                    nrt=(nrt+nr[i][j])%MOD;
            }
    printf ("%d",nrt);
}

int main ()
{
    freopen ("subsir.in","r",stdin);
    freopen ("subsir.out","w",stdout);

    read ();
    solve ();

    return 0;
}