#include <cstdio>
#include <string>
#define maxn 512
#define mod 666013
int dp[maxn][maxn], sol[maxn][maxn];
int n, m;

char a[maxn], b[maxn];

void citire()
{
	freopen("subsir.in", "r", stdin);
	char aux[maxn];
	int i;
	gets(aux);
	n=strlen(aux);
	for(i=0;i<n;i++) a[i+1]=aux[i];
	gets(aux);
	m=strlen(aux);
	for(i=0;i<m;i++) b[i+1]=aux[i];

}

void dynamic()
{
	int i, j;
	for(i=0;i<=n;i++) sol[0][i]=1;
	for(i=0;i<=m;i++) sol[i][0]=1;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(a[i]==b[j]) {dp[i][j]=dp[i-1][j-1]+1;  if(dp[i][j]==1) sol[i][j]=1; else sol[i][j]=sol[i-1][j-1]; sol[i][j]%=mod;}
			else 
			{
				if(dp[i-1][j]==dp[i][j-1]) { dp[i][j]=dp[i-1][j]; if(dp[i-1][j]!=0){ sol[i][j]=sol[i-1][j]+sol[i][j-1], sol[i][j]%=mod;}}
				if(dp[i-1][j]<dp[i][j-1]) dp[i][j]=dp[i][j-1], sol[i][j]=sol[i][j-1], sol[i][j]%=mod;
				if(dp[i-1][j]>dp[i][j-1]) dp[i][j]=dp[i-1][j], sol[i][j]=sol[i-1][j], sol[i][j]%=mod;
			}
		}
				

	/*	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)printf("%d ", sol[i][j]);
		printf("\n");
	}
	*/
		freopen("subsir.out", "w", stdout);
	printf("%d\n", sol[n][m]%mod);
	
}


int main()
{
	citire();
	dynamic();
	
	return 0;
}