# include <stdio.h>
# include <string.h>
# define N 502
# define M 666013 
char a[N], b[N];
int n,m,i,j,A[N][N],Nr[N][N]; 
int main(){
  freopen("subsir.in", "r", stdin);
  freopen("subsir.out", "w", stdout);
  scanf("%s",a+1); n=strlen(a+1);
  scanf("%s",b+1); m=strlen(b+1);
  for (i=0;i<=n;++i) Nr[i][0]=1;
  for (j=0;j<=m;++j) Nr[0][j]=1;
  for (i=1;i<=n;++i)
    for (j=1;j<=m;++j){
       if (a[i]==b[j]){
		A[i][j]=A[i-1][j-1]+1;
		Nr[i][j]=Nr[i-1][j-1];
	       }
       else if (A[i-1][j]>A[i][j-1]){
			A[i][j]=A[i-1][j];
			Nr[i][j]=Nr[i-1][j];
		  }
	    else if (A[i][j-1]>A[i-1][j]){
			  A[i][j]=A[i][j-1];
			  Nr[i][j]=Nr[i][j-1];
		       } 
		  else {
			  A[i][j]=A[i-1][j];
			  Nr[i][j]=(Nr[i][j-1]+Nr[i-1][j])%M;
			  if (A[i-1][j-1]==A[i-1][j])
				Nr[i][j]=(Nr[i][j]-Nr[i-1][j-1])%M;
		       }
    }
  printf("%d",Nr[n][m]);
  return 0;
}