#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nmax=510, mod=666013;
char s[2][nmax];
int prev[2][26][nmax],cml[nmax][nmax],lmax=0,nr[nmax][nmax],last[2][26][nmax];
void preproc()
{
	char c='a';
	int poz=-1,j;
	for(int inc=0;inc<=1;inc++)
		for(int i=0;i<26;i++)
		{
			poz=-1;
			for(j=0;j<(int) strlen(s[inc])-1;j++)
			{
				prev[inc][i][j]=poz;
				if(s[inc][j]==c+i) poz=j;
			}
			last[inc][i][j-1]=poz;
		}
}
void cmlsc()
{
	int len1=strlen(s[0]);
	int len2=strlen(s[1]);
	for(int i=0;i<len1-1;i++)
		for(int j=0;j<len2-1;j++)
			if(s[0][i]==s[1][j])
			{
				cml[i+1][j+1]=cml[i][j]+1;
				if(cml[i][j]==0) nr[i][j]=1;
			}
			else
				cml[i+1][j+1]=max(cml[i+1][j],cml[i][j+1]);
	lmax=cml[len1-1][len2-1];
}
int  solve()
{
	int sol=0;
	int len1=strlen(s[0]),len2=strlen(s[1]);
	for(int i=0;i<len1-1;i++)
		for(int j=0;j<len2-1;j++)
			if(s[0][i]==s[1][j])
				for(int k=0;k<26;k++)
				{
					int ii=prev[0][k][i]+1,jj=prev[1][k][j]+1;
					if(cml[i+1][j+1]==cml[ii][jj]+1)
						nr[i][j]+=nr[ii-1][jj-1],nr[i][j]%=mod;
				} 
	for(int i=0;i<26;i++)
	{
		len1=strlen(s[0])-2,len2=strlen(s[1])-2;
		int ind1=last[0][i][len1],ind2=last[1][i][len2];
		if(cml[ind1+1][ind2+1]==lmax && ind1!=-1 && ind2!=-1)
		{
			sol+=nr[ind1][ind2];
			sol%=mod;
		}
	}
	return sol;
}
int main()
{
	freopen("subsir.in","r", stdin);
	freopen("subsir.out","w",stdout);
	fgets(s[0],nmax,stdin);
	fgets(s[1],nmax,stdin);
	preproc();
	cmlsc();
	printf("%d\n",solve());
}