#include<stdio.h>
#include<string.h>
#define MOD 666013
char s[502],ss[502],lit[27]="abcdefghijklmnoprstuvqwxyz";
int sc[502][501],nr[502][502];
int ps[502][27],pss[501][27];
int n,m;

void pre_gen(){
	int i,k;
	for(i=1;i<=n;i++){
		for(k=0;k<=25;k++){
			ps[i][k]=ps[i-1][k];
			if(s[i]==lit[k]) ps[i][k]=i;
		}
	}

	for(i=1;i<=m;i++){
		for(k=0;k<=25;k++){
			pss[i][k]=pss[i-1][k];
			if(ss[i]==lit[k]) pss[i][k]=i;
		}
	}
}

inline int max(int a,int b){ return(a>b?a:b);}

int solve(){
  int i,j,k,x,y;

  for(i=1;i<=n;i++){
    for(j=1;j<=m;j++){
      if(s[i]==ss[j])
	sc[i][j] = 1 + sc[i-1][j-1];
      else sc[i][j] = max(sc[i-1][j],sc[i][j-1]);
      if(s[i]==ss[j])
      if(sc[i][j]==1 && nr[i][j]==0) nr[i][j]=1;
	for(k=0;k<=25;k++){
		x = ps[i-1][k];
		y = pss[j-1][k];
		    if(sc[x][y]+1==sc[i][j]){
			nr[i][j]+=nr[x][y];
			if(nr[i][j]>=MOD) nr[i][j]-=MOD;
		    }
	}
    }
  }
   return nr[n][m];
}

int main(){

	freopen("subsir.in","rt",stdin);
	freopen("subsir.out","wt",stdout);

	char c;
	while(c!='\n'){ c=getc(stdin);s[++n]=c;}
	c='a';
	while(c!='\n'){ c=getc(stdin);ss[++m]=c;}

	pre_gen();
	printf("%d",solve());

	return 0;
}