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