#include<stdio.h>
#include<srting.h>
#define N 505
#define M 666013
struct nod{long lin;long col;long num;nod *urm;};
nod *prim[N],*p,*q;
char a[N],b[N];
long n,m,i,j,c[N][N],LMAX,L,sol;
void pune(long LUNG,long LIN,long COL,long NUM);
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s%s",a,b);
	n=strlen(a);m=strlen(b);
	if(a[0]==b[0]){c[0][0]=1;pune(1,0,0,1);}
        for(i=1;i<n;i++)if(a[i]==b[0]){c[i][0]=1;pune(1,i,0,1);}
	for(j=1;j<m;j++)if(a[0]==b[j]){c[0][j]=1;pune(1,0,j,1);}
        for(i=1;i<n;i++)
         for(j=1;j<m;j++)
         { c[i][j]=c[i-1][j];
           if(c[i][j]<c[i][j-1])c[i][j]=c[i][j-1];
	   if(a[i]==b[j])
            if(c[i][j]<c[i-1][j-1]+1)c[i][j]=c[i-1][j-1]+1;
           if(a[i]==b[j]) pune(c[i][j],i,j,0);
	   if(LMAX<c[i][j])LMAX=c[i][j];
         }
	if(LMAX>2)
        { for(L=2;L<=LMAX;L++)
           for(p=prim[L-1];p;p=p->urm)
            for(q=prim[L];q;q=q->urm)
             { if(p->lin<q->lin)
                if(p->col<q->col)
                 { q->num+=p->num;
                   q->num%=M;
		 }
	     }
	}
	if(LMAX)
	{ for(p=prim[LMAX];p;p=p->urm)
          { sol+=p->num;
	    sol%=M;
	  }
	}
	printf("%ld\n",sol);
	return 0
}
void pune(long LUNG,long LIN,long COL,long NUM)
{
	nod *paux;
	paux=new nod;
	paux->lin=LIN;
	paux->col=COL;
	paux->num=NUM;
	if(!prim[LUNG]){paux->urm=0;prim[LUNG]=paux;return;}
	paux->urm=prim[LUNG];
	prim[LUNG]=paux;
}