#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[502],b[502];
 
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()
{
    if(a[0]==b[0])
    {
        d[0][0]=1;
        nr[0][0]=1;
    }
    for(int i=1;i<m;i++)
    {
        if(a[i]==b[0])
        {
            d[i][0]=1;
            nr[i][0]=1;
        }
        else
        d[i][0]=d[i-1][0];
    }
    for(int j=1;j<n;j++)
    {
        if(b[j]==a[0])
        {
            d[0][j]=1;
            nr[0][j]=1;
        }
        else
        d[0][j]=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=1;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(a[i]==b[j])
            {
 
                for(int k=0;k<26;k++)
                {
                    pa=preva[i-1][k];
                    pb=prevb[j-1][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 k=0;k<26;k++)
    {
        if(d[preva[m-1][k]][prevb[n-1][k]]==d[m-1][n-1])
        {
            sol+=nr[preva[m-1][k]][prevb[n-1][k]];
            sol%=MOD;
        }
    }
}
 
void afisare()
{
    freopen("subsir.out","w",stdout);
    printf("%d",sol);
}
 
int main()
{
    citire();
    preproc();
    din();
    reconst();
    solutie();
    afisare();
return 0;
}