#include <stdio.h>
#include <string.h>
#define FOR(i,a,b) for (i=a;i<=b;i++)
#define LMAX 630
#define NRMOD 666013
FILE *in,*out;
char s1[LMAX],s2[LMAX];
int x,y,i,j,k;
int a[LMAX][LMAX],b[LMAX][LMAX],nr1[LMAX][30],nr2[LMAX][30],maxv;
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	in=fopen("subsir.in","r");
	out=fopen("subsir.out","w");
	fgets(s1+1,600,in);
	fgets(s2+1,600,in);
	s1[0]=strlen(s1+1);
	s2[0]=strlen(s2+1);
	FOR(i,1,s1[0])
	{
		FOR(j,1,s2[0])
		{
			if (s1[i]==s2[j])
			{
				a[i][j]=a[i-1][j-1]+1;
			}
			else
				a[i][j]=max(a[i-1][j],a[i][j-1]);
			maxv=max(a[i][j],maxv);
		}
	}
	FOR(i,2,s1[0])
	{
		FOR(j,0,25)
			if (s1[i-1]==j+'a')
				nr1[i][j]=i-1;
			else
				nr1[i][j]=nr1[i-1][j];

	}

		FOR(i,2,s2[0])
		{
				FOR(j,0,25)
						if (s2[i-1]==j+'a')
								nr2[i][j]=i-1;
						else
								nr2[i][j]=nr2[i-1][j];

		}
	int rez=0;
	FOR(i,1,s1[0])
		FOR(j,1,s2[0])
		{
			if (s1[i]!=s2[j])
				continue;
			if (a[i][j]==1)
			{
				b[i][j]=1;
				continue;
			}
			FOR(k,0,25)
			{
				x=nr1[i][k];
				y=nr2[j][k];
				if (a[x][y]+1!=a[i][j])
					continue ;
				b[i][j]+=b[x][y];
				b[i][j]%=NRMOD;
			}
		}
	FOR(k,0,25)
	{
		x=nr1[s1[0]][k];
		y=nr2[s2[0]][k];
		if (a[x][y]==maxv)
		{
			rez+=b[x][y];
			rez%=NRMOD;
		}
	}
	fprintf(out,"%d\n",rez);
	fclose(in);
	fclose(out);
	return 0;
}