#include <cstdio>
#include <cstring>
#define N 666013
char a[505],b[505];
int rez,nr[505][505],i,j,n,m,p,c[505][505],la[28][505],lb[28][505];

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s\n%s",a,b);
	n=strlen(a)-1;
	m=strlen(b)-1;
	
	for (i=0;i<=n;++i)
	    for (j=0;j<=m;++j)
			if (a[i]==b[j])
				c[i][j]=c[i-1][j-1]+1; else
					if (c[i-1][j]>c[i][j-1]) 
						c[i][j]=c[i-1][j]; else
							c[i][j]=c[i][j-1];
	
	for (i=0;i<=26;++i)
	{
		for (p=-1,j=0;j<=n;++j)
		{
			if (a[j]=='a'+i) p=j;
			la[i][j]=p;
		}
		
		for (p=-1,j=0;j<=m;++j)
		{
			if (b[j]=='a'+i) p=j;
			lb[i][j]=p;
		}
	}
	
	for (i=0;i<=n;++i)
		for (j=0;j<=m;++j)
			if ((c[i][j]==1) && (a[i]==b[j]))
				nr[i][j]=1;
	
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (a[i]==b[j])
			{
				for (p=0;p<=26;++p)
					if (c[i][j]==c[la[p][i-1]][lb[p][j-1]]+1)
						nr[i][j]=(nr[i][j]+nr[la[p][i-1]][lb[p][j-1]])%N;
				/*if (c[i][j]==c[n][m])	
			    rez=(rez+nr[i][j])%N;*/
			}
	printf("%d",nr[n][m]);
	
	
	return 0;}