#include <stdio.h>
#include <string.h>
char sir1[505],sir2[505];
struct ld
{long x;
 long y;};
ld a[505][505];
long c[505],l,nr,p=1,n,m,i,j,d[505][505];
int main()
{
    freopen ("subsir.in","r",stdin);
    freopen ("subsir.out","w",stdout);
    scanf("%s\n",sir1);n=strlen(sir1);
    scanf("%s\n",sir2);m=strlen(sir2);
    
for(i=n;i>=1;i--)
    for(j=m;j>=1;j--)
        {
        if(sir1[i]==sir2[j])
        {a[i][j].x=a[i+1][j+1].x+1;a[i][j].y=1;}
        else
             if(a[i+1][j].x>a[i][j+1].x)
                {a[i][j].x=a[i+1][j].x; a[i][j].y=a[i][j].y=0;}
             else
                {a[i][j].x=a[i][j+1].x;a[i][j].y=0;}
        }
nr=a[1][1].x;
l=nr;
for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
    {
        if(a[i][j].y==1)
        if(a[i][j].x==l)d[l][i]++;
        else d[--l[i]]++;
    }
    for(i=1;i<=nr;i++)
    p*=c[i];
    printf("%ld",p%666013);
return 0;
}