#include <cstdio>
#include <cstring>
#define nmax 510
#define X 666013

char a[nmax], b[nmax];
int pb[30][nmax], pa[30][nmax], s[nmax][nmax], v[nmax][nmax], sol, r, n, m;

inline int max(int a, int b)
{
	if (a<b) a=b;
	return a;
}

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	int i, j, c;
	fgets(a,nmax,stdin);
	fgets(b,nmax,stdin);
	n=strlen(a)-1;
	m=strlen(b)-1;
	for (i=n; i>0; i--) a[i]=a[i-1]-'a';
	for (i=m; i>0; i--) b[i]=b[i-1]-'a';
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (a[i]==b[j]) 
			{
				s[i][j]=s[i-1][j-1]+1; 
				r=max(r,s[i][j]);
			} else
				s[i][j]=max(s[i-1][j], s[i][j-1]);
	for (i=0; i<26; i++)
	{
		c=0;
		for (j=1; j<=n; j++)
		{
			pa[i][j]=c;
			if (a[j]==i) c=j;
		}
		pa[i][n+1]=c;
		c=0;
		for (j=1; j<=m; j++)
		{
			pb[i][j]=c;
			if (b[j]==i) c=j;
		}
		pb[i][m+1]=c;
	}
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (a[i]==b[j])
				if (s[i][j]==1) v[i][j]=1; else
					for (c=0; c<26; c++)
						if (s[pa[c][i]][pb[c][j]]+1==s[i][j]) v[i][j]=(v[i][j]+v[pa[c][i]][pb[c][j]])%X;
	for (c=0; c<26; c++)
		if (s[pa[c][n+1]][pb[c][m+1]]==r) sol=(sol+v[pa[c][n+1]][pb[c][m+1]])%X;
	printf("%d\n",sol);
}