#include <fstream>
#include <string.h>
#include <vector>
#define NMax 501
#define DIAG 1
#define DR 2
#define JS 3

int lgA, lgB;
char A[NMax], B[NMax];

// PD
struct poz{ int x,y; }aux;
int max, nrmax;
int mat[NMax][NMax];
int op[NMax][NMax];
std::vector<poz> pos;

void citire();
void pd();
void afis();
char* reconst(int x, int y);

int main()
{
	citire();
	pd();
	afis();
	return 0;
}
char* reconst(int x, int y)
{
	int i, j, lg = 1;
	char a[NMax];

	a[0] = A[x];
	while( x < lgA && y < lgB )
	{
		if ( op[x][y] == 1 )
		{
			x++;
			y++;

			if ( x >= lgA || y >= lgB )
				break;
			a[lg++] = A[x];

			continue;
		}
		if ( op[x][y] == JS )
		{
			x++;

			continue;
		}
		if ( op[x][y] == DR )
		{
			y++;

			continue;
		}
	}
	a[lg] = NULL;
	return a;
}
void afis()
{
	long j, maxx = 0;
	int i, ok ;

	char *aux;
	char *p[NMax];

	for (i=0; i<nrmax; i++)
	{
		aux = reconst( pos[i].x, pos[i].y );
		
		ok = 1;
		for (j=0; j<maxx && ok ; j++)
			if ( strcmp( aux, p[j] ) == 0 )
				ok = 0;
		if ( ok )
			p[maxx++] = strdup( aux );
			
	}

	std::ofstream g( "subsir.out" );
	g << maxx % 666013 << '\n'; 
}
void pd()
{
	int i, j;

	for (i=lgA-1; i>=0; i--)
		for (j=lgB-1; j>=0; j--)
		{
			if ( A[i] == B[j] )
			{
				mat[i][j] = 1 + mat[i+1][j+1];
				op[i][j]  = DIAG;

				aux.x = i; aux.y = j;
				if ( mat[i][j] == max )
				{
					pos.push_back( aux );
					nrmax++;
				}
				if ( mat[i][j] > max )
				{
					pos.clear();
					
					pos.push_back( aux );
					nrmax = 1;
					max = mat[i][j];
				}
				continue;
			}
			mat[i][j] = mat[i+1][j];
			op[i][j]  = JS;
			if ( mat[i][j] < mat[i][j+1] )
			{
				mat[i][j] = mat[i][j+1];
				op[i][j]  = DR;
			}

		}
}
void citire()
{
	std::ifstream f( "subsir.in" );
	f >> A >> B ;

	lgA = strlen( A );
	lgB = strlen( B );
}