#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;
}
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 uap[NMAX]={0},ubp[NMAX]={0};
	c1[0]=c2[0]='@';
	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;}
	for(j=0;j<=m;j++){ mat[0][j]=0;l[0][j]=0;}
	for(i=1;i<n;i++)
		for(j=1;j<m;j++)
		{
		    if(c1[i]==c2[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];
	        }
       
	for(i=1;i<n;i++)
	{
	   for(j=1;j<m;j++)
	   {
		 if(mat[i][j]==ll) l[i][j]=1;
		 if(c1[i]==c2[j])
	         for(k=0;k<26;k++)  
			  {
				ii=uap[k];jj=ubp[k];
				if(mat[i][j]==mat[ii][jj]+1) l[i][j]+=(l[ii][jj]%clb);
			  }
	   	 ubp[mki(c2[j])]=j;
	   }
		uap[mki(c1[i])]=i;
        }
        for(i=1;i<n;i++)
	 for(j=1;j<m;j++)
	   if(c1[i]==c2[j])
	   {
     		ii=mki(c1[i]); 
		if(uap[ii]<=i&&ubp[ii]<=j) s+=l[i][j]%clb;
	   }				
        out<<s%clb;
        in.close();out.close();
}