#include <stdio.h>
#include <string.h>
#define N 1<<9
#define NR 666013
char a[N],b[N];
int n,m,c[N][N],last[N][27],last2[N][27],ult[27];
long long nr[N][N],sol;
inline int lit(char x)
{
	return x>='a' && x<='z';
}
inline int max(int a,int b)
{
	return a>=b ? a : b;
}
void cmlsc()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (a[i]==b[j])
				c[i][j]=c[i-1][j-1]+1;
			else
				c[i][j]=max(c[i-1][j],c[i][j-1]);
}
void precompute()
{
	int i,j;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=26; j++)
			last[i][j]=ult[j];
		ult[(int)a[i]-96]=i;
	}
	memset(ult,0,sizeof(ult));
	for (i=1; i<=m; i++)
	{
		for (j=1; j<=26; j++)
			last2[i][j]=ult[j];
		ult[(int)b[i]-96]=i;
	}
}
void solve()
{
	int i,j,k,ii,jj;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (a[i]==b[j])
			{
				if (c[i][j]==1)
					nr[i][j]=1;
				else
					for (k=1; k<=26; k++)
					{
						ii=last[i][k];
						jj=last2[j][k];
						if (c[i][j]==c[ii][jj]+1)
							nr[i][j]+=nr[ii][jj];
						if (nr[i][j]>=NR)
							nr[i][j]%=NR;
					}
				if (c[i][j]==c[n][m])
					sol+=nr[i][j];
				if (sol>=NR)
					sol%=NR;
			}
	printf("%lld\n",sol);
}
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	fgets(a+1,N,stdin);
	while (lit(a[n+1])) n++;
	fgets(b+1,N,stdin);
	while (lit(b[m+1])) m++;
	cmlsc();
	precompute();
	solve();
	return 0;
}