#include <stdio.h>
#include <string.h>
#define lung 500

const int mod = 666013;
char a[lung+5],b[lung+5];
int m[lung][lung],la,lb,mx,Rez;
int r[lung][lung];
int Max[2][lung];
bool ap[256],t[256];

int subsiruri(int x,int y)
{
	int i,j,s;
	s=0;
	for (i=0;i<256;i++)
		ap[i]=0;
	for (i=x;i>=0;i--)
		for (j=y;j>=0;j--)
			if (!ap[b[j]])
			{
				ap[b[j]]=true;
				s= (s+r[i][j])%mod;
			}
	return s;
}

void cmlsc()
{
	int i,j,k,p1,p2;
	mx=0;p1=0;p2=1;
	for (i=0;i<la;i++)
	{
		for (j=0;j<lb;j++)
			if (a[i]==b[j])
			{
				for (k=j-1;k>=0;k--)
					if (m[i][j]<=Max[p2][k])
						m[i][j]=Max[p2][k]+1;
				if (m[i][j]>1)
					r[i][j]= subsiruri(i-1,j);
				else
					r[i][j]=1;
				if (m[i][j]>mx)
					mx=m[i][j];
				Max[p1][j]= (m[i][j]>Max[p1][j]) ? m[i][j] : Max[p1][j];
			}
		for (j=0;j<lb;j++)
			Max[p2][j]=Max[p1][j];
		int tmp = p1;
		p1=p2;
		p2=tmp;
	}
	Rez=0;
	for (i=0;i<la;i++)
		for (j=0;j<lb;j++)
			if (m[i][j]==mx && !t[b[j]])
				Rez= (Rez+r[i][j])%mod,
				t[b[j]]=true;
}

void citire()
{
	freopen("subsir.in","r",stdin);
	fgets( a , lung , stdin );
	fgets( b , lung , stdin );
	la= strlen(a);
	lb= strlen(b);
	while ( a[la-1]=='\n')
		a[la-1]='\0',
		la--;
	while ( b[lb-1]=='\n')
		b[lb-1]='\0',
		lb--;
	fclose(stdin);
}

void scriere()
{
	freopen("subsir.out","w",stdout);
	printf("%d\n",Rez%mod);
	fclose(stdout);
}

int main()
{
	citire();
	cmlsc();
	scriere();
	return 0;
}