#include <stdio.h>
#include <string.h>

int max(int a, int b) {
	if (a < b) return b;
	return a;
}

struct matrice {
	int q, p;
};

int main() {
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);
	char s1[510], s2[510];
	int i, j, k, a[511][511], n, m; 
	int nr[511][511];
	scanf("%s %s", s1, s2);
	n = strlen(s2);
	m = strlen(s1);
	for (i = 0; i <= n;++i) {
		a[i][0] = 0; 
	}

	for (i = 1; i <= m; ++i) {
		a[0][i] = 0;
	}
		
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			if (s2[i - 1] == s1[j - 1]) {
				a[i][j]=1+a[i-1][j-1];
			} else {
				a[i][j] = max(a[i][j - 1], a[i - 1][j]);
			}
		}
	}
	memset(nr, 0, sizeof(nr));
	int sw;
	matrice v[31][511];
	memset(v, 0, sizeof(v));
	for (i = 1; i <= 26;++i) {
		for (j = 1; j <= m; ++j) {
			if (s1[j - 1] == char(i - 1 + (int)'a')) {
				v[i][j].p=j;
			} else {
				v[i][j].p = v[i][j - 1].p;
			}
		}
	}
	for (i = 1;i <= 26; ++i) {
		for (j = 1;j <= n; ++j) {
			if (s2[j - 1] == char(i + (int)'a' - 1)) {
				v[i][j].q = j;
			} else {
				v[i][j].q = v[i][j - 1].q;
			}
		}
	}
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			if (s2[i - 1] == s1[j - 1]) {
				sw = 0;
				for (k = 1; k <= 26; ++k)
					if (v[k][i - 1].q != 0 && v[k][j - 1].p != 0) {
						sw = 1;
						if (a[i][j] == 1 + a[v[k][i - 1].q][v[k][j - 1].p]) {
							nr[i][j] += nr[v[k][i - 1].q][v[k][j - 1].p];
						}
					}
				if (!sw) nr[i][j] = 1;
			}
		}
	}
	int nr1 = 0;
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			if (s1[j - 1] == s2[i - 1] && a[i][j] == a[n][m]) {
				sw = 1;
				for (k = i; k < n; ++k) {
					if (s2[i - 1] == s2[k]) {
						sw=0;
					}
					for (k = j; k < m; ++k) {
						if (s1[j - 1] == s1[k]) {
							sw=0;
						}
					}
					if (sw) {
						nr1 = (nr1 + nr[i][j]) % 666013;
					}
				}
			}
		}
	}
	printf("%d\n", nr1);
	return 0;
}