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

#define nmax 525
#define r 666013


int n, m, c [nmax] [nmax], a [nmax] [nmax], ux [35] [nmax], uy [35] [nmax];
char x [nmax], y [nmax];


void scan ()
{
	scanf ("%s\n%s", x, y);
	n=strlen (x);
	m=strlen (y);
}

inline int max (int x, int y)
{
	if (x > y)
		return x;
	return y;
}

void cmlsc ()
{
	int i, j;
	for (i=1; i <= n; ++i)
		for (j=1; j <= m; ++j)
			if (x [i-1] == y [j-1])
				c [i] [j]=c [i-1] [j-1]+1;
			else
				c [i] [j]=max (c [i-1] [j], c [i] [j-1]);
}

void preg (char x [], int n, int u [] [nmax])
{
	int i, j;
	for (i=1; i <= n; ++i)
		for (j=1; j <= 26; ++j)
			if (x [i-1] == j+'a'-1)
				u [j] [i+1]=i;
			else
				u [j] [i+1]=u [j] [i];
}

int res ()
{
	int i, j, k, w, s=0;
	for (i=1; i <= n; ++i)
		for (j=1; j <= m; ++j)
			if (x [i-1] == y [j-1])
			{
				if (c [i] [j] == 1)
					a [i] [j]=1;
				else
					for (k=1; k <= 26; ++k)
						if (c [ux [k] [i]] [uy [k] [j]] == c [i] [j]-1)
							a [i] [j]=(a [i] [j]+a [ux [k] [i]] [uy [k] [j]])%r;
				w=x [i-1]-'a'+1;
				if ((c [i] [j] == c [n] [m]) && (ux [w] [i] == ux [w] [n]) && (uy [w] [j] == uy [w] [m]))
					s=(s+a [i] [j])%r;
			}
	return s;
}

void print (int x, int y, int a [] [nmax])
{
	int i, j;
	for (i=1; i <= x; ++i)
	{
		for (j=1; j <= y; ++j)
			printf ("%d ", a [i] [j]);
		printf ("\n");
	}
	printf ("\n\n\n");
}

int main ()
{
	freopen ("subsir.in", "r", stdin);
	freopen ("subsir.out", "w", stdout);
	scan ();
	cmlsc ();
	preg (x, n, ux);
	preg (y, m, uy);
	printf ("%d\n", res ());
	
	
	//print (n, m, a);
	
	
	return 0;
}