#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);
	sol[0][0]=1;
	for(i=1;a[i];i++)
		sol[i][0]=1;
	n=i-1;
	for(i=1;b[i];i++)
		sol[0][i]=1;
	m=i-1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			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])
			{
				d[i][j]=d[i-1][j];
				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;
				continue;
			}
			if(d[i-1][j]>d[i][j-1])
			{
				sol[i][j]=sol[i-1][j];
				d[i][j]=d[i-1][j];
			}
			else
			{
				sol[i][j]=sol[i][j-1];
				d[i][j]=d[i][j-1];
			}
		}
	printf("%d\n",sol[n][m]%mod);
	return 0;
}