#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

char a[512],b[512];
long i,j,n,m,c[512][512],nr[512][512],pa[512][30],pb[512][30],ii,jj,rez,k;

long maxim(long a, long b)
{
    if (a>b)
        return a;
    return b;    
}

int main()
{
	
freopen("subsir.in","r",stdin);
freopen("subsir.out","w",stdout);
//citire + prelucrare siruri
scanf("%s",a);
scanf("%s",b);
n=strlen(a);
m=strlen(b);
for (i=n-1;i>=0;i--)
    a[i+1]=a[i]-96;
for (i=m-1;i>=0;i--)
    b[i+1]=b[i]-96;
//preprocesare
for (i=2;i<=n+1;i++)
    {
    for (j=1;j<=26;j++)
        pa[i][j]=pa[i-1][j];
    pa[i][a[i-1]]=i-1;    
    }
for (i=2;i<=m+1;i++)
    {
    for (j=1;j<=26;j++)
        pb[i][j]=pb[i-1][j];        
    pb[i][b[i-1]]=i-1;
    }
//initializare dinamica
if (a[1]==b[1])
    {
    c[1][1]=1;
    nr[1][1]=1;
    }
//dinamica
for (i=1;i<=n;i++)  
    for (j=1;j<=m;j++)   
        if ((i!=1)||(j!=1))
            if (a[i]==b[j])
                {
                c[i][j]=c[i-1][j-1]+1;
                if (c[i][j]==1)
                    nr[i][j]=1;
                }
            else
                c[i][j]=maxim(c[i][j-1],c[i-1][j]);    

for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
        if (a[i]==b[j])
            for (k=1;k<=26;k++)
                {
                ii=pa[i][k];
                jj=pb[j][k];
                if ((c[ii][jj]+1)==c[i][j])   
                    { 
                    nr[i][j]+=nr[ii][jj];
                    nr[i][j]=nr[i][j]%666013;
                    }
                }
for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)  
        if ((c[i][j]==c[n][m])&&(pa[n+1][a[i]]==i)&&(pb[m+1][b[j]]==j))
            {
            rez+=nr[i][j];
            rez=rez%666013;
            }
printf("%d\n",rez);
return 0;
}