#include<stdio.h>
#include<string.h>
#define MOD 666013
int preva[501][27],prevb[501][27],d[501][501],nr[501][501],m,n,sol;
char a[501],b[501];

void citire()
{
    freopen("subsir.in","r",stdin);
    scanf("%s",a);
    scanf("%s",b);
    m=strlen(a);
    n=strlen(b);

}

void preproc()
{
    for(int i=0;i<m;i++)
    {
        a[i]-='a';
    }
    for(int j=0;j<n;j++)
    {
        b[j]-='a';
    }
    for(int i=0;i<26;i++)
    {
        preva[0][i]=501;
        prevb[0][i]=501;
    }
    preva[0][a[0]]=0;
    for(int i=1;i<m;i++)
    {
        memcpy(preva[i],preva[i-1],sizeof(preva[i-1]));
        preva[i][a[i]]=i;
    }
    prevb[0][b[0]]=0;
    for(int i=1;i<n;i++)
    {
        memcpy(prevb[i],prevb[i-1],sizeof(prevb[i-1]));
        prevb[i][b[i]]=i;
    }
}

inline int max(int a,int b)
{
    if(a>b)
    return a;
    return b;
}

void din()
{
    for(int i=0;i<m;i++)
    {
        if(a[i]==b[0])
        d[i][0]=1;
    }
    for(int j=0;j<n;j++)
    {
        if(b[j]==a[0])
        d[0][j]=1;
    }

    for(int i=1;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(a[i]==b[j])
            {
                d[i][j]=d[i-1][j-1]+1;
                if(d[i][j]==1)
                nr[i][j]=1;
            }
            else
            d[i][j]=max(d[i-1][j],d[i][j-1]);
        }
    }
}

void reconst()
{
    int pa,pb;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i]==b[j])
            {
                for(int k=0;k<26;k++)
                {
                    pa=preva[i][k];
                    pb=prevb[j][k];
                    if(d[pa][pb]+1==d[i][j] && pa!=501 && pb!=501)
                    {
                        nr[i][j]+=nr[pa][pb];
                        nr[i][j]%=MOD;
                    }
                }
            }
        }
    }
}

void solutie()
{
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(d[i][j]==d[m-1][n-1] && preva[m-1][a[i]]==i && prevb[n-1][b[j]]==j)
            {
                sol+=nr[i][j];
                sol%=MOD;
            }
        }
    }
}

void afisare()
{
    freopen("subsir.out","w",stdout);
    printf("%d",sol);
}

int main()
{
    citire();
    preproc();
    din();
    reconst();
    solutie();
    afisare();
return 0;
}