#include <stdio.h>
#include <string.h>
int c[505][505],i,j,nr[505][505],n,m,pa[505][30],pb[505][30],ca,sol;
char a[505],b[505];
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s\n",a);
	scanf("%s",b);
	n=strlen(a);
	m=strlen(b);
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (a[i-1]==b[j-1])
				c[i][j]=c[i-1][j-1]+1;
			else
				if (c[i-1][j]>c[i][j-1])
					c[i][j]=c[i-1][j];
				else
					c[i][j]=c[i][j-1];
	for (i=1;i<=n;++i)
		for (ca=1;ca<=26;++ca)
			if (a[i-1]==ca+96)
				pa[i][ca]=i;
			else
				pa[i][ca]=pa[i-1][ca];
	for (i=1;i<=m;++i)
		for (ca=1;ca<=26;++ca)
			if (b[i-1]==ca+96)
				pb[i][ca]=i;
			else
				pb[i][ca]=pb[i-1][ca];
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (a[i-1]==b[j-1])
			{
				if (c[i][j]==1)
					nr[i][j]=1;
				else
				    for (ca=1;ca<=26;++ca)
						if (c[i][j]==c[pa[i-1][ca]][pb[j-1][ca]]+1)
							nr[i][j]+=nr[pa[i-1][ca]][pb[j-1][ca]]%666013;
				if (c[i][j]==c[n][m] && pa[n][a[i-1]-96]==i && pb[m][b[j-1]-96]==j)
				{
					sol+=nr[i][j];
					sol=sol%666013;
				}
			}
	printf("%d",sol);
	return 0;
}