#include<fstream.h>
#include<string.h>

int max(int a,int b)
	{
	if (a<b) return b;
		else return a;
	}

int main()
{
ifstream f("subsir.in");
char s1[502],s2[502];
int i,j,k,a[502][502],nr[502][502],n,m;
f>>s1>>s2;
f.close();
n=strlen(s2);m=strlen(s1);
for (i=0;i<=n;i++) a[i][0]=0; for (i=1;i<=m;i++) a[0][i]=0;
for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
		if (s2[i-1]==s1[j-1]) a[i][j]=1+a[i-1][j-1];
			else a[i][j]=max(a[i][j-1],a[i-1][j]);
memset(nr,0,sizeof(nr));int ii,jj,sw,c; char a1[52],b1[52];
for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
	  if (s2[i-1]==s1[j-1])
		{
		sw=0;
		strncpy(a1,s1,j-1);a1[j-1]=0;
		strncpy(b1,s2,i-1);b1[i-1]=0;
		for (c=((int)'a');c<=((int)'z');c++)
			{
			if (strchr(a1,(char)c)) jj=strrchr(a1,(char)c)-a1+1;
				else jj=0;
			if (strchr(b1,(char)c)) ii=strrchr(b1,(char)c)-b1+1;
				else ii=0;
			if (ii && jj) {
				      sw=1;
				      if (a[i][j]==1+a[ii][jj]) nr[i][j]+=nr[ii][jj];
				      }
			}
		if (!sw) nr[i][j]=1;
		}
long nr1=0;
for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
		if (s1[j-1]==s2[i-1] && a[i][j]==a[n][m]) {
							  sw=1;
							  for (k=i;k<n;k++)
								if (s2[i-1]==s2[k]) sw=0;
							  for (k=j;k<m;k++)
								if (s1[j-1]==s1[k]) sw=0;
							  if (sw) nr1=(nr1+nr[i][j])%666013;
							  }
ofstream g("subsir.out");
g<<nr1;
g.close();
return 0;
}