/* Se cere: lungimea celui mai lung subsir crescator.*/
#include <fstream>
using namespace std;

char a[501], b[501];
int c[501];
int m, n;
int L_max;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

void Read();
void Solve();
void Write();

int main()
{
	Read();
	Solve();
	Write();
	fin.close();
	fout.close();
	return 0;
}

void Read()
{
	fin >> a >> b;
	m = strlen(a);
	n = strlen(b);
}

void Solve()
{
	int k;
	for ( int i = 1; i <= m; i++)
		for ( int j = 1; j <= n; j++)
			if ( a[i] == b[j]  )
			{
				for ( c[j] = 1, k = 0; k < j; k++)
					if( b[k] < b[j] && c[j] < c[k] + 1 )
						c[j] = c[k] + 1;
				L_max = max( L_max, c[j] );
			}
}

void Write()
{
	fout << L_max % 666013 << '\n';
}