#include<stdio.h>
#include<string.h>
#define mod 666013
FILE*f=fopen("subsir.in","r");
FILE*g=fopen("subsir.out","w");
int c[501][100], nr[502][502],n,m, pozi[29], pozj[29];
char a[501],b[502];
void read()
	{
	fscanf(f,"%s\n%s",a,b);
	n=strlen(a);
	m=strlen(b);
	int i,j;
	for(i=n;i>0;--i) a[i]=a[i-1];
	for(i=m;i>0;--i) b[i]=b[i-1];
	}
void subsir_comun()
	{
	int i,j;
	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;
			}
		 else if (c[i][j-1]>c[i-1][j]) c[i][j]=c[i][j-1];
		 else c[i][j]=c[i-1][j];
	}
int verif(int p, int k)
	{
	int i,j;
	if(a[p]!=b[k]) return 0;
	for(i=p+1;i<=n;++i)
		for(j=k+1;j<=m;++j)
			if(a[i]==a[p]&&b[k]==b[j]) return 0;
	return 1;
	}
void det_solutie()
	{
	int i,j,ii,jj,x,y,k;
	char p;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)

			if(a[i]==b[j]&&c[i][j]==1) nr[i][j]=1;

			else if(a[i]==b[j])
				{
				for(p='a';p<='z';++p)
				    {
				    pozi[p-96]=-1;
				    for(k=1;k<i;++k)
					if(a[k]==p) pozi[p-96]=k;
				    pozj[p-96]=-1;
				    for(k=1;k<j;++k)
					if(b[k]==p) pozj[p-96]=k;
				    }
				for(p='a';p<='z';++p)
					{
					if(pozi[p-96]!=-1&&pozj[p-96]!=-1)
					    {
					    ii=pozi[p-96]; jj=pozj[p-96];
					    if(c[i][j]==c[ii][jj]+1) nr[i][j]=(nr[i][j]+nr[ii][jj])%mod;
					    }
					}
				}
	}
void det_rez_final()
	{
	int i,j,rez=0;
	/*for(i=1;i<=n;++i)
	       {
		for(j=1;j<=m;++j)
		       {
		       fprintf(g,"%d ",nr[i][j]);
		       if(verif(i,j)) rez=(rez+nr[i][j])%mod;
		       }
		fprintf(g,"\n");
		}       */
	fprintf(g,"%d",nr[n][m]);
	}
int main()
	{
	read();
	subsir_comun();
	det_solutie();
	det_rez_final();
	return 0;
	}