#include<cstdio>
#include<cstring>
char a[505],b[505];
int d[505][505],s[505][505];
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    int n,m,i,j,md;
    md=666013;
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    s[0][0]=1;
    for(i=1;i<=n;i++)
        s[i][0]=1;
    for(j=1;j<=m;j++)
        s[0][j]=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            if(a[i]==b[j])
        {
            d[i][j]=(d[i-1][j-1]+1)%md;
            s[i][j]=s[i-1][j-1];
        }
        else
        {
            if(d[i-1][j]>d[i][j-1])
            {
                d[i][j]=d[i-1][j];
                s[i][j]=s[i-1][j];
            }
            if(d[i-1][j]<d[i][j-1])
            {
                d[i][j]=d[i][j-1];
                s[i][j]=s[i][j-1];
            }
            if(d[i-1][j]==d[i][j-1])
            {
                d[i][j]=d[i-1][j];
                s[i][j]=(s[i-1][j]+s[i][j-1])%md;
                if(d[i][j]==d[i-1][j-1])
                    s[i][j]=s[i][j]-s[i-1][j-1];
                if(s[i][j]<0)
                    s[i][j]=s[i][j]+md;
            }
        }
        printf("%d\n",s[n][m]);
  return 0;
}