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