#include<stdio.h>
#define REST 666013
char a[512],b[512];
int ss[512][512],sol[512][512],pa[512][32],pb[512][32];
int n,m;
inline int max(int x,int y){
	return x>y?x:y;
}
int main(){
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	int i,j,k;
	fgets(a+1,510,stdin);
	fgets(b+1,510,stdin);
	for(n=1;'a'<=a[n] && a[n]<='z';++n);
	--n;
	for(m=1;'a'<=b[m] && b[m]<='z';++m);
	--m;
	
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			if(a[i]==b[j])
				ss[i][j]=1+ss[i-1][j-1];
			else
				ss[i][j]=max(ss[i-1][j],ss[i][j-1]);
		}
	}
	
	for(i=1;i<=n;++i){
		for(k=0;k<26;++k){
			pa[i][k]=pa[i-1][k];
		}
		pa[i][a[i]-'a']=i;
	}
	for(i=1;i<=m;++i){
		for(k=0;k<26;++k){
			pb[i][k]=pb[i-1][k];
		}
		pb[i][b[i]-'a']=i;
	}
	
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			for(k=0;k<26;++k){
				if(a[i]==b[j] && ss[i][j]==1)
					sol[i][j]=1;
				else{
					if(1+ss[pa[i][k]][pb[j][k]]==ss[i][j]){
						sol[i][j]+=sol[pa[i][k]][pb[j][k]];
						if(sol[i][j]>=REST)
							sol[i][j]-=REST;
					}
				}
			}
		}
	}
	
	printf("%d\n",sol[n][m]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}