#include<stdio.h>
#include<string.h>
#define NMAX 501
char a[NMAX],b[NMAX];
int sol[NMAX][NMAX];
void read()
{
	FILE*f=fopen("subsir.in","r");
	fgets(a,NMAX,f);
	fgets(b,NMAX,f);
	fclose(f);
}
int maxim(int a,int b)
{
	if(a>=b)return a;
	return b;
}
int main()
{
	read();
	int i,j,max=-1,cont=0,n,m;
	n=strlen(a)-1;
	m=strlen(b)-1;
	for(i=1;i<=n;++i)
	for(j=1;j<=m;++j)
	{
		if(a[i-1]==b[j-1])
		{
			sol[i][j]=1+sol[i-1][j-1];
			if(sol[i][j]==max)++cont;
			else if(sol[i][j]>max){max=sol[i][j];cont=1;}
		}
		else sol[i][j]=maxim(sol[i][j-1],sol[i-1][j]);
		
	}
	FILE*g=fopen("subsir.out","w");
	fprintf(g,"%d\n",cont%666013);
	fclose(g);
	return 0;
}