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

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

int a,b,i,j,k,V[dim][dim],S[dim][dim],PA[130][dim],PB[130][dim];
char A[dim],B[dim];

int maxim(int h , int j){
	if(h>j)
		return h;
	return j;
}

int main(){
	
	fscanf(f,"%s\n",A+1);
	fscanf(f,"%s",B+1);
	a=strlen(A+1);
	b=strlen(B+1);
	
	
	for(i=2;i<=a;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<=b;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<=a;i++){
		for(j=1;j<=b;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[a][b]);
	return 0;
}