#include <stdio.h>
#define Nmax 502
#define sigma 27
#define Mod 666013

int C[Nmax][Nmax],Nr[Nmax][Nmax];
int Last[2][Nmax][sigma],Lg[2];
char s[2][Nmax];
int sol,mxl;

inline int Maxim(int x,int y){ return x>y ? x:y; }

void pre(int wh){
	int i,j;
	
	for(i=1; i<=Lg[wh]; ++i){
		for( j=0; j<sigma; ++j) 
			Last[wh][i][j]=Last[wh][i-1][j];
		Last[wh][i][s[wh][i]-'a']=i;
	}
}

void din(){
	int i,j;
	for(i=1;i<=Lg[0];++i)
		for(j=1;j<=Lg[1];++j){
			C[i][j]=Maxim(C[i-1][j],C[i][j-1]);
			if( s[0][i] == s[1][j] ) C[i][j]=Maxim(C[i][j],C[i-1][j-1]+1);
			if( C[i][j]==1) Nr[i][j]=1;
			mxl=Maxim(mxl,C[i][j]);
		}
}

void solve(){
	int i,j,k;
	
	for(i=1;i<=Lg[0];++i)
		for(j=1;j<=Lg[1];++j)
			if( s[0][i] == s[1][j] )
				for(k=0; k<sigma; ++k)
					if( C[Last[0][i-1][k]][Last[1][j-1][k]] == C[i][j]-1 )
						Nr[i][j] =( Nr[i][j] + Nr[Last[0][i-1][k]][Last[1][j-1][k]]) % Mod;
						
	
	for(k=0;k<sigma;++k) 
		if( C[Last[0][Lg[0]][k]][Last[1][Lg[1]][k]] == mxl )
			sol =( sol + Nr[Last[0][Lg[0]][k]][Last[1][Lg[1]][k]]) % Mod;
}

int main(){
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s\n%s\n",s[0]+1,s[1]+1);
	for(Lg[0]=1; s[0][Lg[0]] >='a' && s[0][Lg[0]]<='z'; ) ++Lg[0]; --Lg[0];
	for(Lg[1]=1; s[1][Lg[1]] >='a' && s[1][Lg[1]]<='z'; ) ++Lg[1]; --Lg[1];
	
	pre(0); pre(1);
	din();
	solve();
	
	printf("%d\n",sol);
	fclose(stdin); fclose(stdout);
	return 0;
}