#include <stdio.h>
#include <string.h>
#define M 666013

char a[502], b[502];
int n, m , i, j, A[502][502], Nr[502][502];

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

	scanf ("%s",a + 1);
	n = strlen (a + 1);
	scanf ("%s", b +1);
	m = strlen (b + 1);

	for (i = 0;i <= n; ++i)
		Nr[i][0] = 1;

	for (j = 0;j <= m; ++j)
		 Nr[0][j] = 1;

	for (i = 1;i <= n; ++i)
		for (j = 1;j <= m; ++j)
		{
			if (a[i] == b[j])
			{
				A[i][j] = A[i - 1][j - 1] + 1;
				Nr[i][j] = Nr[i - 1][j - 1];
			}
			else
			if (A[i - 1][j] > A[i][j - 1])
			{
				A[i][j] = A[i - 1][j];
				Nr[i][j] = Nr[i - 1][j];
			}
			else
			if (A[i][j - 1] > A[i - 1][j])
			{	
				A[i][j] = A[i][j - 1];
				Nr[i][j] = Nr[i][j - 1];
			}
			else
			{
				A[i][j] = A[i - 1][j];
				Nr[i][j] = (Nr[i][j - 1] + Nr[i - 1][j])%M;
				if (A[i - 1][j - 1] == A[i - 1][j])
					Nr[i][j] = (Nr[i][j] - Nr[i - 1][j - 1] + M) % M;
			}
		}
	printf ("%d", Nr[n][m]);
	return 0;
}