#include <bits/stdc++.h>
using namespace std;

FILE *f1 = fopen("subsir.in", "r");
FILE *f2 = fopen("subsir.out", "w");

const int kMax = 505, MOD = 666013;

int main() {

	char a[kMax], b[kMax];
	int dp_len[kMax][kMax], dp_sol[kMax][kMax];
	int i, j, l1, l2;
	fscanf(f1, "%s\n", (a+1));
	fscanf(f1, "%s", (b+1));
	l1 = strlen(a);
	l2 = strlen(b);
		
	for (i = 0; i < kMax; i++)
		for (j = 0; j < kMax; j++) {
			dp_len[i][j] = 0;
			dp_sol[i][j] = 0;
		}
	//calculate lengths
	for (i = 1; i <= l1; i++)
		for (j = 1; j <= l2; j++)
			if (a[i] == b[j]) {
				dp_len[i][j] = 1 + dp_len[i-1][j-1];
			}
			else {
				dp_len[i][j] = max(dp_len[i-1][j], dp_len[i][j-1]);
			}
	
	//calculate distinct common subsequences

	//empty substring is always common
	for (i = 0; i <= l1; i++)
		dp_sol[i][0] = 1;
	for (i = 0; i <= l2; i++)
		dp_sol[0][i] = 1;

	for (i = 1; i <= l1; i++)
		for (j = 1; j <= l2; j++)
			if (a[i] == b[j]) {
				//all substrings already found + the new common character
				dp_sol[i][j] = dp_sol[i-1][j-1];
			}
			else {
				if (dp_len[i][j] == dp_len[i-1][j])
					dp_sol[i][j] = (dp_sol[i][j] + dp_sol[i-1][j]) % MOD;
				if (dp_len[i][j] == dp_len[i][j-1])
					dp_sol[i][j] = (dp_sol[i][j-1] + dp_sol[i][j]) % MOD;
				if (dp_len[i][j] == dp_len[i-1][j-1])
					dp_sol[i][j] = (dp_sol[i][j] - dp_sol[i-1][j-1] + MOD) % MOD;
			}
	fprintf(f2, "%d\n", dp_sol[l1][l2]);
	fclose(f1);
	fclose(f2);
	return 0;
}