#include<stdio.h>
#include<string.h>
#define Nmax 505
#define MOD %666013
#define max(a,b) ((a>b)? a:b)

int n,m,i,j,a[Nmax][Nmax],s[Nmax][Nmax];
char s1[Nmax],s2[Nmax];

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	
	gets(s1);
	n=strlen(s1);
	for (i=n;i>=1;i--)
		s1[i]=s1[i-1];

	gets(s2);
	m=strlen(s2);
	
	for (i=m;i>=1;i--)
		s2[i]=s2[i-1];

	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (s1[i]==s2[j])
			{
				a[i][j]=a[i-1][j-1]+1;
				s[i][j]=s[i-1][j-1];
			}
			else if (a[i][j-1]==a[i-1][j])
			{
				s[i][j]=(a[i][j-1]+a[i-1][j])MOD;
				a[i][j]=a[i][j-1];
			}
			else
			{
				a[i][j]=max(a[i][j-1],a[i-1][j-1]);
				s[i][j]=max(s[i][j-1],s[i-1][j-1]);
			}

	printf("%d\n",s[n][m]+1);
	return 0;
}