#include<stdio.h>
#define M 501
long sol[M][M],fr[M][M],i,j,n,m;
char a[M],b[M];

int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    a[0]='w';b[0]='w';


    scanf("%c",&a[1]);
    for(n=2;a[n-1]!='\n';n++)
	scanf("%c",&a[n]);
    n--;n--;

    scanf("%c",&b[1]);
    for(m=2;b[m-1]!='\n';m++)
	scanf("%c",&b[m]);

    m--;m--;
    
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (a[i]==b[j])
            {
			   sol[i][j]=sol[i-1][j-1]+1;
			   if (fr[i-1][j-1]==0)
				fr[i][j]=1;
			   else
			   	fr[i][j]=fr[i-1][j-1];
	    }
	    else
	    {
		if (sol[i-1][j]==sol[i][j-1])
		{
		   sol[i][j]=sol[i-1][j];
		   fr[i][j]=fr[i-1][j];
		   fr[i][j]+=fr[i][j-1];
		   fr[i][j]%=666013;
		}
                else
                    if (sol[i-1][j]>sol[i][j-1])
                    {
						sol[i][j]=sol[i-1][j];
						fr[i][j]=fr[i-1][j];
                    }
                    else
                        {
						    sol[i][j]=sol[i][j-1];
						    fr[i][j]=fr[i][j-1];
			}
	    }
    printf("%ld\n",fr[n][m]);
    return 0;
}