#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define ii prec1[i][k]
#define jj prec2[j][k]

const int MOD = 666013;
const int MAX_N = 510;
const int SIGMA = 28;

int n, m;
char a[MAX_N], b[MAX_N];
int d[MAX_N][MAX_N], c[MAX_N][MAX_N];
int prec1[MAX_N][SIGMA], prec2[MAX_N][SIGMA];

int main()
{
	int i, j, k;
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);

	scanf("%s\n", a);
	scanf("%s\n", b);

	n = strlen(a);
	m = strlen(b);

	for (i = 0; i < n; ++i)
		a[i] = a[i] - 'a' + 1;

	for (i = 0; i < m; ++i)
		b[i] = b[i] - 'a' + 1;

	for (i = 1; i <= n; ++i)
	{
		for (j = 1; j <= 26; ++j)
			prec1[i][j] = prec1[i - 1][j];

		prec1[i][a[i - 1]] = i - 1;
	}

	for (i = 1; i <= m; ++i)
	{
		for (j = 1; j <= 26; ++j)
			prec2[i][j] = prec2[i - 1][j];

		prec2[i][b[i - 1]] = i - 1;
	}

	if (a[0] == b[0])
		c[0][0] = d[0][0] = 1;

	for (i = 0; i < n; ++i)
		for (j = 0; j < m; ++j)
			if ((i != 0) || (j != 0))
				if (a[i] == b[j])
				{
				//	printf("praf%d %d\n", i, j);
					c[i][j] = c[i - 1][j - 1] + 1;
					if (c[i][j] == 1) 
						d[i][j] = 1;
				}
				else c[i][j] = max(c[i - 1][j], c[i][j - 1]);

	for (i = 0; i < n; ++i)
		for (j = 0; j < m; ++j)
			if (a[i] == b[j])
				for (k = 1; k <= 26; ++k)
					d[i][j] =  (c[i][j] == c[ii][jj] + 1) ? (d[i][j] + d[ii][jj]) % MOD : d[i][j];

	int sol = 0;

	for (i = 0; i < n; ++i)
		for (j = 0; j < m; ++j)
			if ((c[i][j] == c[n - 1][m - 1]) && (prec1[n][a[i]] == i) && (prec2[m][b[j]] == j))
				sol = (sol + d[i][j]) % MOD;

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