#include<stdio.h>
#include<string.h>

#define NMAX 505
#define MOD 666013
#define maxim(a,b) (a>b ? a : b)

char s1[NMAX],s2[NMAX];
int d[NMAX][NMAX],count[NMAX][NMAX];
int n1,n2;

int main ()
{
	int  i,j;
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s",s1+1);
	scanf("%s",s2+1);
	n1=strlen(s1+1);
	n2=strlen(s2+1);
	count[0][0]=1;
	for(i=1;i<=n1;i++)
		for(j=1;j<=n2;j++)
		{
			if(s1[i]==s2[j])
			{
				d[i][j]=d[i-1][j-1]+1;
				count[i][j]=count[i-1][j-1];
				continue;
			}
			d[i][j]=maxim(d[i][j-1],d[i-1][j]);
			if(d[i][j-1]>d[i-1][j])
				count[i][j]=count[i][j-1];
			else if(d[i][j-1]<d[i-1][j])
				count[i][j]=count[i-1][j];
			else
			{
				count[i][j]=count[i-1][j]+count[i][j-1];		
				if(d[i-1][j-1]==d[i][j-1])
					count[i][j]-=count[i-1][j-1];
				if(count[i][j]<0)
					count[i][j]+=MOD;
				if(count[i][j]>=MOD)
					count[i][j]-=MOD;		
			}	
			if(!d[i][j])
				count[i][j]=1;
		}
	printf("%d\n",count[n1][n2]);	
	return 0;
}