#include <cstdio>
#include <cstring>

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

int n, m;
int d[MAX_N][MAX_N], s[MAX_N][MAX_N];
char a[MAX_N], b[MAX_N];

int main()
{
	int i, j;
	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 = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			if (a[i] == b[j])
			{
				d[i][j] = d[i - 1][j - 1] + 1;
				s[i][j] = 1;
			}
			else
				if (d[i - 1][j] > d[i][j - 1])
				{
					d[i][j] = d[i - 1][j];
					s[i][j] = (s[i][j] + s[i - 1][j]) % MOD;
				}
				else
				{
					d[i][j] = d[i][j - 1];
					s[i][j] = (s[i][j] + s[i][j - 1]) % MOD;
				}

	int sol = 0;

	for (i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			if (d[i][j] == d[n][m])
				sol = (sol + s[i][j]) % MOD;

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