#include<fstream>
#include <iostream>
#include <string>
#include<ctime> 
using namespace std;

int i, j, k, n, m, m1, gasit, mai_e;
string sir1, sir2, sir_mare, sir_mic, gasite[30];
clock_t start, end;
size_t found;


int main()
{
	start = clock();
	ifstream f("subsir.in");
	ofstream g("subsir.out");
	f>>sir1>>sir2;
//	g<<sir1<<" "<<sir2<<"\n";
	n=sir1.length();
	m=sir2.length();
	if (n>m)
	{
		sir_mare=sir1;
		sir_mic=sir2;
		m1=m;
	}
	else
	{
		sir_mare=sir2;
		sir_mic=sir1;
		m1=n;
	}
//	g<<sir_mare<<" "<<sir_mic<<"\n"<<m1<<"\n";
	for (i=m1;i>=2;i--)
	{
		gasit=0;
		for (j=0;j<=m1-i;j++)
		{
//			g<<sir_mic.substr(j,i)<<" - ";
			found=sir_mare.find(sir_mic.substr(j,i));
//			g<<int(found)<<"\n";
			if (int(found)!=-1)
			{
//				g<<"gasit\n";
				for (k=1;k<=gasit;k++)
				{
					mai_e=0;
//					g<<sir_mic.substr(j,i)<<" "<<gasite[k]<<"\n";
					if (sir_mic.substr(j,i)==gasite[k])
					{
						mai_e=1;
//						g<<"mai e\n";
					}
				}
				gasit=gasit+1-mai_e;
				gasite[gasit]=sir_mic.substr(j,i);
			}
		}
		if (gasit>0)
		{
//			for (k=1;k<=29;k++)
//				g<<"gasite["<<k<<"]="<<gasite[k]<<"\n";
			g<<gasit%666013;
			return 0;
		}
	}
		
	return 0;
}