#include<cstdio>
#include<cstring>
#define mod 666013
char v[501],v2[501];
int ma[501][501],d[501][501];
int max(int a, int b)
    {if(a>=b)
        return a;
    return b;
    }
int main ()
{freopen ("subsir.in","r",stdin);
freopen ("subsir.out","w",stdout);
int n,m,i,j;
scanf("%s%s",&v,&v2);
n=strlen(v);
m=strlen(v2);
for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        if(v[i]==v2[j])
            ma[i][j]=ma[i-1][j-1]+1;
        else
            ma[i][j]=max(ma[i-1][j],ma[i][j-1]);
for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        {if(i==0||j==0)
            d[i][j]=1;
        else
            if(v[i]==v2[j])
                d[i][j]=d[i-1][j-1];
            else
                {if(ma[i-1][j]==ma[i][j])
                    d[i][j]=(d[i-1][j]+d[i][j])%mod;
                if(ma[i][j-1]==ma[i][j])
                    d[i][j]=(d[i][j-1]+d[i][j])%mod;
                if(ma[i-1][j-1]==ma[i][j])
                    d[i][j]=(d[i][j]-d[i-1][j-1]+mod)%mod;
                }
        }
printf("%d",d[n-1][m-1]);
return 0;
}