#include<stdio.h>
#define mod 666013
int n,m;
int d[512][512],sol[512][512];
char a[512],b[512];

inline int max(int a, int b, int c)
{
	if(a<b)
		a=b;
	if(a<c)
		a=c;
	return a;
}

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	int i,j;
	gets(a+1);
	gets(b+1);
	for(i=1;a[i];i++)
		sol[i][0]=1;
	n=i;
	for(i=1;b[i];i++)
		sol[0][i]=1;
	m=i;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			d[i][j]=max(d[i-1][j],d[i-1][j-1],d[i][j-1]);
			if(a[i]==b[j])
			{
				d[i][j]=d[i-1][j-1]+1;
				sol[i][j]=sol[i-1][j-1];
				continue;
			}
			if(d[i-1][j]==d[i][j-1])
			{
				sol[i][j]=sol[i-1][j]+sol[i][j-1];
				if(sol[i][j]>=mod)
					sol[i][j]-=mod;
				if(d[i][j-1]==d[i-1][j-1])
					sol[i][j]-=sol[i-1][j-1];
				if(sol[i][j]<0)
					sol[i][j]+=mod;
			}
			if(d[i-1][j]>d[i][j-1])
				sol[i][j]=sol[i-1][j];
			else
				sol[i][j]=sol[i][j-1];
		}
	printf("%d\n",sol[n][m]%mod);
	return 0;
}