#include<fstream>
using namespace std;
ofstream g("subsir.out");

int i,j,n,m,l[502][502],uz[50];
char a[502],b[502];
void form()
{
	int i,j;
	l[0][0]=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i-1]==b[j-1])
				l[i][j]=l[i-1][j-1]+1;
			else
				if(l[i][j-1]<l[i-1][j])
					l[i][j]=l[i-1][j];
				else
					l[i][j]=l[i][j-1];
}
void det()
{
	int i,j,k,ix=n,iy=m,nr;
	unsigned long max1=0;
	for(k=l[n][m];k>=1;k--)
	{
		for(i=0;i<=30;i++)
			uz[i]=0;
		nr=0;
		for(i=n;i>=1;i--)
			for(j=m;j>=1;j--)
				if(l[i][j]==k&&a[i-1]==b[j-1])
				{
					if(!uz[a[i-1]-97+1])
					uz[a[i-1]-97+1]=1,nr++;
				}
				else
					if(l[i][j]<k)
					    break;
				if(max1<nr)
						max1=nr;
	}
	g<<max1%666013;
}
int main()
{
	ifstream f("subsir.in");
	f.getline(a,502);
	f.getline(b,502);
	n=strlen(a);
	m=strlen(b);
	form();
	det();
	return 0;
}