#include<cstdio>
#include<string>
#define l 502
#define mod 666013
using namespace std;

void citeste();
void rezolva();
void afiseaza();


char a[l],b[l],m[l][l],id[l][l];
int na,nb;
int nr=0;


void citeste()
{
	freopen("subsir.in","r",stdin);
	
	gets(a);
	gets(b);
	
	char aux[l];
	
	strcpy(aux,a);
	strcpy(a+1,aux);
	
	strcpy(aux,b);
	strcpy(b+1,aux);
	
	na=strlen(a)-1;
	nb=strlen(b)-1;
	
	
	fclose(stdin);
}


void rezolva()
{
	int i,j;
	
	for( i=0;i<=na;i++) m[0][i]=0;
	for( i=1;i<=nb;i++) m[i][0]=0;
	
	for(i=1;i<=nb;i++)
		for(j=1;j<=na;j++)
		{
			if(a[j]==b[i]) 
			{
				m[i][j]=m[i-1][j-1]+1;
				id[i][j]=1;
			}
			else
			{
				if(m[i-1][j]>m[i][j-1])
				{
					m[i][j]=m[i-1][j];
					id[i][j]=2;
				}
				else
				{
					m[i][j]=m[i][j-1];
					id[i][j]=3;
				}
			}
		}

int max=m[nb][na];


for(i=1;i<=na;i++)
{
	if(m[nb][i]==max)
	{
		if(id[nb][i]==1)
		{
			if(id[nb-1][i-1]!=-1) 
			{
				nr++;
				id[nb-1][i-1]=-1;
			}
			id[nb][i]=-1;
		}
		
		else if(id[nb][i]==2)
		{
			if(id[nb-1][i]!=-1) 
			{
				nr++;
				id[nb-1][i]=-1;
			}
			id[nb][i]=-1;
		}
		else 
		{
			if(id[nb][i-1]!=-1) 
			{
				nr++;
				id[nb][i-1]=-1;
			}
			id[nb][i]=-1;
		}
		nr%=mod;
	}
}

}

void afiseaza()
{
	freopen("subsir.out","w",stdout);
	
	printf("%d",nr);
	
	fclose(stdout);
}


int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}