#include<fstream>
#include<string>
#include<algorithm>
using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");
#define rest 666013

string A,B;
int N,M,D[505][505];
long long sol=1;

void find(int x,int y){
	if(x!=1 && y!=1){
		if(A[x-1]==B[y-1]){
			find(x-1,y-1);
		}
		else{
			if(D[x-1][y]==D[x][y-1]){
				sol++;
				find(x-1,y);
				find(x,y-1);
			}
			if(D[x-1][y]>D[x][y-1])
				find(x-1,y);
			if(D[x-1][y]<D[x][y-1])
				find(x,y-1);
		}
	}
}

int main(){
	int i,j;
	
	fin>>A>>B;
	N=A.size();
	M=B.size();
	
	for(i=1;i<=N;i++){
		for(j=1;j<=M;j++){
			if(A[i-1]==B[j-1])
				D[i][j]=1+D[i-1][j-1];
			else{
				D[i][j]=max(D[i-1][j],D[i][j-1]);
			}
		}
	}
	
	find(N,M);
	
	fout<<sol%rest<<"\n";
	
	fin.close();
	fout.close();
	return 0;
}