#include <stdio.h>
#include <string.h>

#define Dim 505
#define MOD 666013

char A[Dim],B[Dim];
int D[2][Dim],sol[2][Dim];

int main()
{
	int i,j,nA,nB;

	freopen("subsir.in","r",stdin);

	fgets(A,Dim,stdin);
	fgets(B,Dim,stdin);

	nA=strlen(A)-1;
	nB=strlen(B)-1;

	memset(D,0,sizeof(D));
	memset(sol,0,sizeof(sol));
	for(i=0;i<=nB;i++) sol[0][i]=1;
	sol[1][0]=1;

	for(i=1;i<=nA;i++)
	{
		for(j=1;j<=nB;j++)
			if(A[i-1]==B[j-1])
			{
				D[1][j]=D[0][j-1]+1;
				sol[1][j]=sol[0][j-1];
			}
			else
			if(D[0][j]>D[1][j-1])
			{
				D[1][j]=D[0][j];
				sol[1][j]=sol[0][j];
			}
			else
			if(D[0][j]<D[1][j-1])
			{
				D[1][j]=D[1][j-1];
				sol[1][j]=sol[1][j-1];
			}
			else
			if(D[0][j]==D[1][j-1])
			{
				D[1][j]=D[0][j];
				sol[1][j]=(sol[0][j]+sol[1][j-1])%MOD;
				if(D[0][j]==D[0][j-1]) sol[1][j]=(sol[1][j]-sol[0][j-1]+MOD)%MOD;
			}
		for(j=1;j<=nB;j++)
		{
			D[0][j]=D[1][j];
			D[1][j]=0;
			sol[0][j]=sol[1][j];
			sol[1][j]=0;
		}
	}

	freopen("subsir.out","w",stdout);

	printf("%d\n",sol[0][nB]);

	return 0;
}