#include <fstream>
#include <cstring>

using namespace std;

const char InFile[]="subsir.in";
const char OutFile[]="subsir.out";
const int MaxN=505;
const int MOD=666013;
const int SIGMA=26;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,indA[MaxN][SIGMA],indB[MaxN][SIGMA],D[MaxN][MaxN],C[MaxN][MaxN];
char A[MaxN],B[MaxN];

int main()
{
	fin>>(A+1)>>(B+1);
	fin.close();

	N=strlen(A+1);
	M=strlen(B+1);

	for(register int i=1;i<=N;++i)
	{
		for(register int j=0;j<SIGMA;++j)
		{
			indA[i][j]=indA[i-1][j];
		}
		indA[i][A[i]-'a']=i;
	}

	for(register int i=1;i<=M;++i)
	{
		for(register int j=0;j<SIGMA;++j)
		{
			indB[i][j]=indB[i-1][j];
		}
		indB[i][B[i]-'a']=i;
	}
	
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=M;++j)
		{
			if(A[i]==B[j])
			{
				D[i][j]=D[i-1][j-1]+1;
			}
			else
			{
				D[i][j]=max(D[i-1][j],D[i][j-1]);
			}
		}
	}

	C[0][0]=1;
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=M;++j)
		{
			if(D[i][j]==1)
			{
				C[i][j]=1;
				continue;
			}
			for(register int k=0;k<SIGMA;++k)
			{
				int ii=indA[i-1][k];
				int jj=indB[j-1][k];
				if(D[i][j]==D[ii][jj]+1)
				{
					C[i][j]+=C[ii][jj];
					C[i][j]%=MOD;
				}
			}
		}
	}

	fout<<C[N][M];
	fout.close();
	return 0;
}