#include <fstream>
#define DIM 510 
#define MOD 666013
using namespace std;

char A[DIM];
char B[DIM];

int V[DIM][DIM], W[DIM][DIM], S[DIM][DIM], D[DIM][DIM];

int N, M, i, j, k, pa, pb;

int main() {
	ifstream f("subsir.in");
	ofstream g("subsir.out");
	f>>A+1;
	f>>B+1;
	N = strlen(A+1);
	M = strlen(B+1);
	A[++N] = 'z'+1;
	B[++M] = 'z'+1;
//	char dz = 'z' + 1;
	
	for (k='a';k<='z';k++)
		for (i=1;i<=N;i++)
			if (A[i-1] == k)
				V[i][k] = i-1;
			else
				V[i][k] = V[i-1][k];
	for (k='a';k<='z';k++)
		for (i=1;i<=M;i++)
			if (B[i-1] == k)
				W[i][k] = i-1;
			else
				W[i][k] = W[i-1][k];
	
	S[0][0] = 1;
	for (i=1;i<=N;i++)
		for (j=1;j<=M;j++) {
			if (A[i] == B[j]) {
				D[i][j] = D[i-1][j-1] + 1;
			} else 
				if (D[i-1][j] > D[i][j-1]) {
					D[i][j] = D[i-1][j];
				} else {
					D[i][j] = D[i][j-1];
				}
			if (D[i][j] == 1) {
				S[i][j] = 1;
				continue;
			}
			for (k = 'a';k<='z';k++) {
				pa = V[i][k];
				pb = W[j][k];
				if (D[i][j] == D[pa][pb] + 1) {
					S[i][j] += S[pa][pb];
					if (S[i][j] >= MOD)
						S[i][j] -= MOD;
				}
			}
		}
	
	g<<S[N][M];		
	return 0;
}