#include<fstream>
using namespace std;
char a[501],b[501],sol[500];
int d[501][501],n,i,j,m,bst,nr,ok,bstmax,k,ok1=1;
int max(int a, int b)
{
	if(a>b)
		return a;
	else
		return b;
}
int main()
{
	ifstream f("subsir.in");
	ofstream g("subsir.out");
	f.getline(a,501);
	f.getline(b,501);
	n=strlen(a);
	m=strlen(b);
	while(ok1)
	{
		bst=0;
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				if(a[i]==b[j])
					d[i][j]=d[i-1][j-1]+1;
				else
					d[i][j]=max(d[i-1][j],d[i][j-1]);
		i=n-1;
		j=m-1;
		while(i>=0)
		{
			if(a[i]==b[j])
			{
				sol[bst]=a[i];
				bst++;
				i--;
				j--;
			}
			else
				if(d[i-1][j]<d[i][j-1])
					j--;
				else
					i--;
		}
		if(!ok)
		{
			bstmax=bst;
			ok=1;
			nr--;
		}
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				d[i][j]=0;
			nr++;
		for(i=0;i<bst;i++)
			for(j=0;j<n;j++)
				if(sol[i]==a[j])
				{
					for(k=j;k<n-1;k++)
						a[k]=a[k+1];
					n--;
				}
		for(i=0;i<bst;i++)
			for(j=0;j<m;j++)
				if(sol[i]==b[j])
				{
					for(k=j;k<n-1;k++)
						b[k]=b[k+1];
					m--;
				}
		for(i=0;i<bst;i++)
			sol[i]=NULL;
		if(bst!=bstmax)
			ok1=0;
	}
	g<<nr%666013;
}