#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; int 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]); //algoritmul de programare dinamica


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;   //in matricea v.p am calculat ultimele aparitii ale literelor a..z in sirul s1 :v[1][j].p reprezinta ultima aparitie a literei 'a' in sirul s1[j-1]

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;   //in v.q am calculat ultimele aparitii ale lit in sirul s2


for (i=1;i<=n;i++)                        //am construit matricea nr
	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[v[k][i-1].q][v[k][j-1].p];
							      }
		if (!sw) nr[i][j]=1;
		}


long nr1=0;
for (i=1;i<=n;i++)                 // am calculat rezultatul final in nr1
	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;
}