#include<stdio.h>
#include<string.h>
#define dim 600
#define mod 666013

int i,j,n,m,k,V[dim][dim],PA[dim][dim],PB[dim][dim],S[dim][dim];
char A[dim],B[dim];


FILE*f=fopen("subsir.in","r");
FILE*g=fopen("subsir.out","w");

void read(){
	fscanf(f,"%s\n",A+1);
	fscanf(f,"%s",B+1);
	n=strlen(A+1);
	m=strlen(B+1);
}

int maxim(int t1,int t2){
	if(t1>t2)
		return t1;
	return t2;
}

int main(){
	read();
	
	for(i=2;i<=n;i++){
		for(k='a';k<='z';k++)
			PA[k][i]=PA[k][i-1];
		
		PA[(int)A[i-1]][i]=i-1;
	}
	
	for(i=2;i<=m;i++){
		for(k='a';k<='z';k++)
			PB[k][i]=PB[k][i-1];
		
		PB[(int)B[i-1]][i]=i-1;
	}
	
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(A[i]==B[j]){
				V[i][j]=V[i-1][j-1]+1;
				if(V[i][j]==1)
					S[i][j]=1;
				else{
					for(k='a';k<='z';k++){
						if(V[PA[k][i]][PB[k][j]]+1==V[i][j]){
							S[i][j]+=S[PA[k][i]][PB[k][j]]%mod;
							S[i][j]%=mod;
						}
					}
				}
			}
			else{
				V[i][j]=maxim(V[i-1][j],V[i][j-1]);
			}
		}
	}
	
	fprintf(g,"%d",S[n][m]);
	
	return 0;
}