#include <cstdio>
#include <cstring>

#define MAX_N 505
#define SIGMA 26
#define MOD 666013

char A[MAX_N], B[MAX_N];
int Nr[MAX_N][MAX_N], C[MAX_N][MAX_N], Pa[SIGMA][MAX_N], Pb[SIGMA][MAX_N];

inline int max(const int &A, const int &B)
{
	return ((A) > (B))? (A) : (B);
}

int main()
{
	freopen("subsir.in","rt",stdin);
	freopen("subsir.out","wt",stdout);

	fgets(A+1, MAX_N, stdin);
	fgets(B+1, MAX_N, stdin);

	int N = strlen(A+1);
	if(A[N] == '\n') --N;

	int M = strlen(B+1);
	if(B[M] == '\n') --M;

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			C[i][j] = ((A[i] == B[j])? C[i-1][j-1] + 1 : max(C[i-1][j], C[i][j-1]));

	//fprintf(stderr, "%d %d\n%d\n", N, M, C[N][M]);
	memset(Pa, -1, sizeof Pa);
	memset(Pb, -1, sizeof Pb);
	for(int i = 1; i <= N; ++i)
		for(int c = 0; c < 26; ++c)
			Pa[c][i] = ((A[i] == (c+'a'))? i : Pa[c][i-1]);

	for(int j = 1; j <= M; ++j)
		for(int c = 0; c < 26; ++c)
			Pb[c][j] = ((B[j] == (c+'a'))? j : Pb[c][j-1]);

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
		{
			if(C[i][j] == 1) 
				Nr[i][j] = 1;

			for(int c = 0; c < 26; ++c)
			{
				int anti = Pa[c][i-1];
				int antj = Pb[c][j-1];

				if(anti == -1 || antj == -1) continue;

				if(C[i][j] == C[anti][antj] + 1)
					Nr[i][j] = (Nr[i][j] + Nr[anti][antj]) % MOD;
			}
		}

	/*for(int i = 1; i <= N; ++i)
	{
		for(int j = 1; j <= M; ++j)
			fprintf(stderr,"%d ", Nr[i][j]);
		fprintf(stderr,"\n");
	}*/

	int Sol = 0;
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			if((C[i][j] == C[N][M]) && (A[i] == B[j]))
			{
				int anti = Pa[A[i]-'a'][N];
				int antj = Pb[B[j]-'a'][M];

				if(i == anti && j == antj)
					Sol = (Sol + Nr[i][j]) % MOD;
			}

	printf("%d\n",Sol);
}