#include<stdio.h>
#include<string.h>
#define N 505
#define M 666013
int n1,n2;
char c1[N],c2[N];
int a[N][N];
int nr[N][N];
short pre1[N][26],pre2[N][26];
short poz1[26],poz2[26];
int rez;
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
        fgets(c1+1,N,stdin);
	fgets(c2+1,N,stdin);
	while(c1[n1+1]>='a' && c1[n1+1]<='z')
	{
		++n1;
		memcpy(pre1[n1],poz1,26*sizeof(short));
		poz1[c1[n1]-'a']=n1;
	}
	while(c2[n2+1]>='a' && c2[n2+1]<='z')
	{
		++n2;
		memcpy(pre2[n2],poz2,26*sizeof(short));
		poz2[c2[n2]-'a']=n2;
	}
	for(int i=1; i<=n1; ++i)
	{
		for(int j=1; j<=n2; ++j)
		{
			if(c1[i]==c2[j])
			{
				a[i][j]=a[i-1][j-1]+1;
				if(a[i][j]==1)
				{
					++nr[i][j];
					continue;
				}
				for(int t=0; t<26; ++t)
				{
					if(a[pre1[i][t]][pre2[j][t]]+1==a[i][j])
						nr[i][j]+=nr[pre1[i][t]][pre2[j][t]];
					if(nr[i][j]>=M)
						nr[i][j]-=M;
				}
			}
			else
			{
				if(a[i-1][j]>a[i][j-1])
					a[i][j]=a[i-1][j];
				else
					a[i][j]=a[i][j-1];
			}
		}
	}
	for(int i=0; i<26; ++i)
	{
		if(a[poz1[i]][poz2[i]]==a[n1][n2])
	      	{
		      rez+=nr[poz1[i]][poz2[i]];
	      		if(rez>=M)
		  		rez-=M;
		}
	}
	printf("%d\n",rez);
	return 0;
}