#include <stdio.h>
#include <algorithm>

using namespace std;

#define NMAX 512
#define SIGMA 255
#define MOD 666013

int din[NMAX][NMAX];
int cnt[NMAX][NMAX];
int lstA[NMAX][SIGMA],lstB[NMAX][SIGMA];
char A[NMAX],B[NMAX];
int n,m;

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);

	int i,j=0,x,y,c;

	fgets(A,NMAX,stdin);
	fgets(B,NMAX,stdin);

	for (n=0;(A[n]>='a')&&(A[n]<='z');n++);
	for (m=0;(B[m]>='a')&&(B[m]<='z');m++);

	for (i=1;i<=n;i++) 
		for (j='a';j<='z';j++)
			if (A[i-1]==j) lstA[i][j]=i;
				else lstA[i][j]=lstA[i-1][j];

	for (i=1;i<=m;i++) 
		for (j='a';j<='z';j++)
			if (B[i-1]==j) lstB[i][j]=i;
				else lstB[i][j]=lstB[i-1][j];

	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			if (A[i-1]!=B[j-1]) {din[i][j]=max(din[i-1][j],din[i][j-1]);continue;}

			din[i][j]=din[i-1][j-1]+1;
			if (din[i][j]==1) {cnt[i][j]=1;continue;}
		
			cnt[i][j]=0;
			for (c='a';c<='z';c++)
			{
				x=lstA[i][c];
				y=lstB[j][c];
			
				if ( x&&y&&(din[x][y]+1==din[i][j]) ) cnt[i][j]=(cnt[i][j]+cnt[x][y])%MOD;
			}
		}

/*	for (i=1;i<=n;i++,printf("\n"))
		for (j=1;j<=m;j++)
			printf("%d ",din[i][j]);
	printf("\n");
	for (i=1;i<=n;i++,printf("\n"))
		for (j=1;j<=m;j++)
			printf("%d ",cnt[i][j]);*/

	int sol=0;

	for (c='a';c<='z';c++)
		{
			x=lstA[n][c];
			y=lstB[m][c];
				
			if ( x&&y&&(din[x][y]==din[n][m]) ) sol=(sol+cnt[x][y])%MOD;
		}
	printf("%d",sol);
	return 0;
}