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

#define NMAX 501
#define FIN "subsir.in"
#define FOUT "subsir.out"
#define MOD 666013

int N,M;
char A[NMAX],B[NMAX];
int i,j;
int nr[NMAX][NMAX],c[NMAX][NMAX];

void read()
{

freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);

scanf("%s", A+1);
scanf("%s", B+1);

N=strlen(A+1);
M=strlen(B+1);

for (i=0;i<=N;i++)
    c[i][0]=1;
for (j=0;j<=M;j++)
    c[0][j]=1;
}

void write()
{
printf("%d",c[N][M]);
}

void programare_dinamica()
{

for (i=1;i<=N;i++)
    for (j=1;j<=M;j++)
	{
	  if (A[i]==B[j])
	      {
		nr[i][j]=nr[i-1][j-1]+1;
		c[i][j]=c[i-1][j-1];
		}
		else
		   if (nr[i-1][j]==nr[i][j-1])
		       {
			nr[i][j]=nr[i-1][j];
			c[i][j]=(c[i-1][j]+c[i][j-1])%MOD;
			  if (nr[i-1][j]==nr[i-1][j-1])
			     c[i][j]=(c[i][j]-c[i-1][j-1]+MOD)%MOD;

			 }
			  else
			     if (nr[i-1][j]>nr[i][j-1])
				 {
				  nr[i][j]=nr[i-1][j];
				  c[i][j]=c[i-1][j];
				  }
				   else
				      if (nr[i-1][j]<nr[i][j-1])
					 {
					  nr[i][j]=nr[i][j-1];
					  c[i][j]=c[i][j-1];
					  }
				      }
}

int main()
{
read();
programare_dinamica();
write();
return 0;
}