#include<fstream>
using namespace std;
int n,m,i,j,pos,a[501][501],p[501],l,ok;
char s1[501],s2[501],s[501][501];
int main()
{
	ifstream f("subsir.in");
	ofstream g("subsir.out");
	f.get(s1,501);
	f.get();
	f.get(s2,501);
	n=strlen(s1);
	m=strlen(s2);
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			if(s1[i-1]==s2[j-1])
			{
				a[i][j]=a[i-1][j-1]+1;
				ok=1;
				if(!p[a[i][j]])
				{
					p[a[i][j]]=1;
					s[p[a[i][j]]][a[i][j]]=s1[i-1];
				}
				else
				{
				  for(l=1;l<=p[a[i][j]];l++)
				     if(s[l][a[i][j]]==s1[i-1])
					       ok=0;
					   if(ok==1)
					   {
						 p[a[i][j]]=p[a[i][j]]+1;
						 s[p[a[i][j]]][a[i][j]]=s1[i-1];
						}
				}
			}
			else
				if(a[i-1][j]>a[i][j-1])
					a[i][j]=a[i-1][j];
				else
					a[i][j]=a[i][j-1];
	}
	pos=1;
	for(l=1;l<=a[n][m];l++)
		pos=(pos*p[l])%666013;
		g<<pos;
	return 0;
}