#include <cstdio>
#include <cstring>

const int mod=666013;

char a[502],b[502];
int c[501][501],d[501][501];

 int main()
 {
    int n,m,i,j;
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    fgets(a+1,sizeof(a+1),stdin);
    fgets(b+1,sizeof(b+1),stdin);
    m=strlen(a+1);
    n=strlen(b+1);
    for (i=0;i<=m;++i)
        d[0][i]=1;
    for (i=0;i<=n;++i)
        d[i][0]=1;
    for (i=1;i<=m;++i)
        for (j=1;j<=n;++j)
            if (a[i]==b[j])
            {
                c[i][j]=c[i-1][j-1]+1;
                d[i][j]=d[i-1][j-1]%mod;
            }
            else if (c[i][j-1]>c[i-1][j])
            {
                c[i][j]=c[i][j-1];
                d[i][j]=d[i][j-1]%mod;
            }
            else
            {
                c[i][j]=c[i-1][j];
                if (c[i-1][j]>c[i][j-1])
                    d[i][j]=d[i-1][j]%mod;
                else if (c[i-1][j-1]==c[i-1][j])
                    d[i][j]=(d[i][j]-d[i-1][j-1])%mod;
                else
                    d[i][j]=(d[i][j-1]+d[i-1][j])%mod;
            }
    printf("%d\n",d[m][n]);
    return 0;
}