#include<stdio.h>
#include<string.h>
#define N 50
#define M 666013
char a[N],b[N],cc,*cit;
long n,m,i,j,k,c[N][N],pa[N][30],pb[N][30],LMAX,ii,jj,nr[N][N],ok,sol;
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	a[0]=b[0]='a';
	cit=&a[1];scanf("%s",cit);n=strlen(cit);
	cit=&b[1];scanf("%s",cit);m=strlen(cit);
	for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	   { if(a[i]==b[j])
	      {c[i][j]=c[i-1][j-1]+1;continue;}
	     c[i][j]=(c[i-1][j]>c[i][j-1])?c[i-1][j]:c[i][j-1];
	   }

	LMAX=c[n][m];
	for(k=0;k<26;k++)
	{ cc=(char)k+'a';
	  for(i=1;i<=n;i++)
	   pa[i+1][k]=(a[i]==cc)?i:pa[i][k];
	  for(j=1;j<=m;j++)
	   pb[j+1][k]=(b[j]==cc)?j:pb[j][k];
	}
	for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	  if(a[i]==b[j])
	    { ok=0;
	      for(k=0;k<26;k++)
	      { ii=pa[i][k];jj=pb[j][k];
		if(ii&&jj)
		{ ok=1;
		  if(c[i][j]==(c[ii][jj]+1))
		   nr[i][j]=(nr[i][j]+nr[ii][jj])%M;
		}
	      }
	    if(!ok)nr[i][j]=1;
	 }
	for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	  if(a[i]==b[j]&&c[i][j]==LMAX)
	  { k=(long)(a[i]-'a');
	    if(pa[n+1][k]==i&&pb[n+1][k]==j)
	      sol=(sol+nr[i][j])%M;
	  }
	printf("%ld\n",sol);
	return 0;
}