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

using namespace std;

#define MAXN 512
#define prim 666013

char A[MAXN], B[MAXN];
int n, m, i, j, k, p, q, sol;
int prec_a[32][MAXN], prec_b[32][MAXN];
char alf[32];
int c[MAXN][MAXN], d[MAXN][MAXN];

void cit() {
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);

	scanf("%s", A + 1);
    A[0] = ' ';
    n = strlen(A) - 1;

	scanf("%s", B + 1);
	B[0] = ' ';
	m = strlen(B) - 1;
}

void solve() {
	//c[i][j] = cel mai lung subir comun daca folosesc primele i din A si primele j din B
	for (i = 0; i <= n; i++)
		for (j = 0; j <= m; j++) {
			if (i <= n && j <= m && A[i + 1] == B[j + 1])
				c[i + 1][j + 1] = max(c[i + 1][j + 1], c[i][j] + 1);
			c[i][j + 1] = max(c[i][j + 1], c[i][j]);
			c[i + 1][j] = max(c[i + 1][j], c[i][j]);
		}

	//precalculez prima a aparitiei literei i inaintea de pozitia j
	for (i = 'a'; i <= 'z'; i++)
		alf[i - 'a' + 1] = i;
	
	for (i = 1; i <= 26; i++)
		for (j = 1; j <= n; j++)
			if (A[j] == alf[i]) prec_a[i][j] = j;
			else prec_a[i][j] = prec_a[i][j - 1];

	for (i = 1; i <= 26; i++)
		for (j = 1; j <= m; j++)
			if (B[j] == alf[i]) prec_b[i][j] = j;
			else prec_b[i][j] = prec_b[i][j - 1];

	//calculez numarul de subsiruri distincte folosind primele i din A si j din B, care au ultima litera A[i] = B[j]
	d[0][0] = 1;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			if (A[i] == B[j])
				if (c[i][j] == 1) d[i][j] = 1;
				else 
					for (k = 1; k <= 26; k++) {
 						p = prec_a[k][i - 1]; q = prec_b[k][j - 1];

						if (c[i][j] == c[p][q] + 1)
							d[i][j] = (d[i][j] + d[p][q]) % prim;
					}
}

void write() {           
	//calculez solutia
	for (i = 1; i <= 26; i++) {
		p = prec_a[i][n]; q = prec_b[i][m];

		if (c[p][q] == c[n][m]) 
			sol += d[p][q];
	}

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

int main() {

    cit();
	solve();
	write();

	return 0;
}