#include<stdio.h>
#include<string.h>
int n,m,i,j,a[501][501],s[501][501];
char s1[501],s2[501];
int main()
{
freopen("subsir.in","r",stdin);
freopen("subsir.out","w",stdout);
scanf("%s\n",s1+1);
scanf("%s\n",s2+1);
n=strlen(s1+1);
m=strlen(s2+1);

for(i=0;i<=500;i++)a[i][0]=1,a[0][i]=1,s[i][0]=1,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-1][j]==a[i][j-1])
		{
		 a[i][j]=a[i-1][j];
		 s[i][j]=(s[i-1][j]+s[i][j-1])%666013;
		 if(a[i-1][j-1]==a[i-1][j])
			 s[i][j]=(s[i][j]-s[i-1][j-1]+666013)%666013;
		}
	else if(a[i-1][j]<a[i][j-1])
		{
		 a[i][j]=a[i][j-1];
		 s[i][j]=s[i][j-1];
		}
	else if(a[i][j-1]<a[i-1][j])
		{
		 a[i][j]=a[i-1][j];
		 s[i][j]=s[i-1][j];
		}
printf("%d",s[n][m]);
return 0;
}