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

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

struct matrice {
	       int q,p;
	       };

int main()
{
ifstream f("subsir.in");
char s1[510],s2[510];
int i,j,k,a[511][511],n,m; long nr[511][511];
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 sw,c;
matrice v[31][511];
memset(v,0,sizeof(v));
for (i=1;i<=26;i++)
	for (j=1;j<=m;j++)
		if (s1[j-1]==char(i-1+(int)'a')) v[i][j].p=j;
			else v[i][j].p=v[i][j-1].p;
for (i=1;i<=26;i++)
	for (j=1;j<=n;j++)
		if (s2[j-1]==char(i+(int)'a'-1)) v[i][j].q=j;
			else v[i][j].q=v[i][j-1].q;
	for (j=1;j<=m;j++)
	  if (s2[i-1]==s1[j-1])
		{
		sw=0;
		for (k=1;k<=26;k++)
			if (v[k][i-1].q!=0 && v[k][j-1].p!=0) {
							      sw=1;
							      if (a[i][j]==1+a[v[k][i-1].q][v[k][j-1].p]) nr[i][j]=(nr[i][j]+nr[v[k][i-1].q][v[k][j-1].p])%666013;
							      }
		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;
}