#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=0;i<=500;i++)
		a[i][0]=a[0][i]=s[i][0]=s[0][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]=(s[i-1][j]+s[i][j-1])%MOD;				
				if(a[i-1][j-1]==a[i-1][j])
					s[i][j]=(s[i][j]-s[i-1][j-1]+MOD)%MOD;
				a[i][j]=a[i][j-1];
			}
			else if (a[i][j-1]>a[i-1][j-1])
			{
				a[i][j]=a[i][j-1];
				s[i][j]=s[i][j-1];
			}
			else 
			{
				a[i][j]=a[i-1][j];
				s[i][j]=s[i-1][j];
			}

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