#include<stdio.h>
#include<string.h>
char s1[505],s2[505];
long c[505][505],a[505],b[505],last1[505][27],last2[505][27],nr[505][505],
ii,jj,sol,max,i,j,k,l1,l2,m;
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s%s",s1,s2);m=666013;
	l1=strlen(s1);l1=strlen(s2);
        for(i=0;i<l1;i++)a[i+1]=(long)(s1[i]-'a')+1;
	for(i=0;i<l2;i++)b[i+1]=(long)(s2[i]-'a')+1;
	for(i=1;i<=l1;i++)
         for(j=1;j<=l2;j++)
          { c[i][j]=(c[i-1][j]>c[i][j-1])?c[i-1][j]:c[i][j-1];
            if(a[i]==b[j]&&(c[i][j]<c[i-1][j-1]+1))
	    c[i][j]=c[i-1][j-1]+1;
	  }
             
	max=c[l1][l2];
	for(i=1;i<=l1;i++)
	{
		for(j=1;j<=26;j++)last1[i][j]=last1[i-1][j];
		last1[i][a[i]]++;
	}   
        for(i=1;i<=l2;i++)
	{
		for(j=1;j<=26;j++)last2[i][j]=last2[i-1][j];
		last2[i][b[i]]++;
	}   
        for(i=1;i<=l1;i++)
	 for(j=1;j<=l2;j++)
	  if(a[i]==b[j])
	  { for(k=1;k<=26;k++)
	    { ii=last1[i-1][k];
	      jj=last2[j-1][k];
	      if(c[ii][jj]==c[i][j]-1)
                 nr[i][j]=(nr[i][j]+nr[ii][jj])%m;
	    }
	    if(c[i][j]==max)sol=(sol+nr[i][j])%m;
          } 
	printf("%ld",sol);
	return 0;
}