#include<stdio.h>
char a[502], b[502];
int x[501][501];
long y[501][501],s;
int m,n,i,j,k,u,v,w;
void f()
{
	int i,j;
	for (i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++)
				printf("%d ",x[i][j]);
		printf("\n");
	}
	printf("\n");
}
void g()
{
	int i,j;
	printf("\n");
	for (i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++)
				printf("%d ",y[i][j]);
		printf("\n");
	}
	printf("\n");
}

int main()
{
freopen("subsir.in","r",stdin);
freopen("subsir.out","w",stdout);

scanf("%s\n%s",a+1,b+1);

m=1;while (a[m])m++;
n=1;while (b[n])n++;
a[m]='t';
b[n]='t';
for (j=0;j<=n;j++)x[0][j]=0;
for (i=0;i<=m;i++)x[i][0]=0;
for (i=1;i<=m;i++)
	{
	for (j=1;j<=n;j++)
		if (a[i]==b[j]) {x[i][j]=1+x[i-1][j-1];}
			else if (x[i-1][j]>x[i][j-1]) {x[i][j]=x[i-1][j];}
				else {x[i][j]=x[i][j-1];}
	}
for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
				if (a[i]!=b[j])
						x[i][j]=0;
//f();
for (i=1;i<=m;i++)
	for (j=1;j<=n;j++)
		{
		y[i][j]=0;
		if (x[i][j]==1 && a[i]==b[j]) y[i][j]=1;
		}
for (k=2;k<=x[m][n];k++)
	{
	s=0;
	for (i=m;i>=1;i--)
		for (j=n;j>=1;j--)
			if (x[i][j]==k && a[i]==b[j])
				{
				w=1;
				for (u=i-1;u>=1;u--)
					for (v=j-1;v>=w;v--)
						if (x[u][v]==k-1 && a[u]==b[v])
							{
							y[i][j]=(y[i][j]+y[u][v])%666013;
							w=v+1;
							break;
							}
				s=(s+y[i][j])%666013;
				}
	if (k==x[m][n])printf("%ld",s);
	}
//g();
fclose(stdin);
fclose(stdout);
return 0;
}