#include <fstream>
#define NMAX 512
#define INF "subsir.in"
#define OUF "subsir.out"
#define clb 666013
using namespace std;
unsigned mki(char c)
{
	return (unsigned)c-97;
}
int main()
{
	fstream in(INF,ios::in);
	fstream out(OUF,ios::out);
	char c1[NMAX],c2[NMAX];
	unsigned long mat[NMAX][NMAX],l[NMAX][NMAX],i,j,n,m,k,ii,jj,ll=0,s=0;
	unsigned a[NMAX],b[NMAX],uap[NMAX][26]={0},ubp[NMAX][26]={0};
	c1[0]=c2[0]='a';
	in>>(c1+1);in>>(c2+1);
	n=strlen(c1);m=strlen(c2);
	for(i=0;i<n;i++){ mat[i][0]=0;l[i][0]=0;a[i]=mki(c1[i]);} 
	for(j=0;j<m;j++){ mat[0][j]=0;l[0][j]=0;b[j]=mki(c2[j]);}
	for(i=1;i<n;i++)
		for(j=1;j<m;j++)
		{
		    if(a[i]==b[j]) mat[i][j]=mat[i-1][j-1]+1;
		    else{
			      if(mat[i-1][j]>mat[i][j-1]) mat[i][j]=mat[i-1][j];
		                else mat[i][j]=mat[i][j-1];
			}	
		    if(mat[i][j]>ll) ll=mat[i][j];
	        }
	//printf("\n");

	for(k=0;k<26;k++)
	{
           for(i=1;i<n;i++) if(a[i]==k) uap[i][k]=i;
	                      else uap[i][k]=uap[i-1][k];
	   for(j=1;j<m;j++) if(b[j]==k) ubp[j][k]=j;
	                      else ubp[j][k]=ubp[j-1][k];
	}
	
        
        for(i=1;i<n;i++)
		for(j=1;j<m;j++) if(mat[i][j]==1) l[i][j]=1;
	for(i=1;i<n;i++)
	{
	   for(j=1;j<m;j++)
	   {
		 //if(mat[i][j]==ll) l[i][j]=1;
		 if(a[i]==b[j])
	         for(k=0;k<26;k++)  
			  {
				ii=uap[i-1][k];jj=ubp[j-1][k];
				if(mat[i][j]==mat[ii][jj]+1) l[i][j]=(l[i][j]+l[ii][jj])%clb;
			  }
	   	 
	   }
		
        }
	/*for(i=1;i<n;i++)
	{
		for(j=1;j<m;j++) printf("%d ",mat[i][j]);
		printf("\n");
	}
	printf("\n");
        for(i=1;i<n;i++)
	{
		for(j=1;j<m;j++) printf("%d ",l[i][j]);
		printf("\n");
	}*/
        for(i=1;i<n;i++)
	 for(j=1;j<m;j++)
	   if(a[i]==b[j]&&mat[i][j]==ll)
	   {
     		ii=a[i]; 
		if(uap[n-1][ii]==i&&ubp[m-1][ii]==j) s=(s+l[i][j])%clb;
	   }				
        out<<s%clb;
        in.close();out.close();
}