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

#define NMAX 510

char a[NMAX], b[NMAX];
int max[NMAX][NMAX];
long nr[NMAX][NMAX];
int n, m;

void read()
{
	scanf("%s\n", a+1);
	scanf("%s\n", b+1);
	n = strlen(a+1);
	m = strlen(b+1);
}
long dinamic()
{
	int i, j;
	long next;

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			if(a[i] == b[j])
			{
				next = max[i-1][j-1] + 1;

				if(max[i][j] == next)
				{
					++nr[i][j];
				}
				else
				{
					max[i][j] = next;
					nr[i][j] = 1;
				}
			}
			else if(max[i-1][j] > max[i][j-1])
			{
				max[i][j] = max[i-1][j];
				nr[i][j] = nr[i-1][j];
			}
			/*else if(max[i-1][j] == max[i][j-1])
			{
				max[i][j] = max[i-1][j] + max[i][j-1];
			}
			*/
			else
			{
				max[i][j] = max[i][j-1];
				nr[i][j] = nr[i][j-1];
			}

			if(nr[i][j] >= 666013)
				nr[i][j] -= 666013;
		}
	}
	return (nr[n][m] % 666013);
}






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

	read();

	printf("%ld\n", dinamic());

	fclose(stdin);
	fclose(stdout);

	return 0;
}