#include<stdio.h>
#define MOD 666013
char a[550],b[550];
int nr[510][510],lung[30],numar[30];
int n,m;
void calcul(){
	int i;
	for(i=1;'a'<=a[i] && a[i]<='z';++i)
		++m;
	for(i=1;'a'<=b[i] && b[i]<='z';++i)
		++n;
}
inline int max(int a,int b){
	return a>b?a:b;
}
void calclung(){
	int i,j;
	for(i=1;i<=m;++i){
		for(j=1;j<=n;++j){
			if(a[i]==b[j])
				nr[i][j]=1+nr[i-1][j-1];
			else
				nr[i][j]=max(nr[i-1][j],nr[i][j-1]);
		}
	}
}
void solve(){
	int i,j,k,sol=0;
	calclung();
	for(i=1;i<=m;++i){
		for(j=1;j<=n;++j){
			if(a[i]==b[j]){
				if(nr[i][j]==1){
					lung[a[i]-'a']=1;
					numar[a[i]-'a']=1;
				}
				else{
					if(lung[a[i]-'a']<nr[i][j]){
						numar[a[i]-'a']=0;
						for(k=0;k<26;++k){
							if(lung[k]==nr[i][j]-1 && a[i]-'a'!=k){
								lung[a[i]-'a']=nr[i][j];
								numar[a[i]-'a']=(numar[a[i]-'a']+numar[k])%MOD;
							}
						}
					}
				}
			}
		}
	}
	for(i=0;i<26;++i)
		if(lung[i]==nr[m][n])
			sol+=numar[i];
	printf("%d\n",sol%MOD);
}
int main(){
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	
	fgets(a+1,550,stdin);
	fgets(b+1,550,stdin);
	calcul();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}