#include<stdio.h>
#define NMAX 520
#define sigma 32
#define MOD 666013

char S1[NMAX],S2[NMAX];
int A[NMAX],B[NMAX];

int V1[sigma][2],V2[sigma][2];

//vector< int > P1[sigma],P2[sigma];

int C[NMAX][NMAX],NR[NMAX][NMAX];


inline int max(const int a,const int b)
{
	return a>b?a:b;
}

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	
	gets( S1 );
	gets( S2 );
	
	//reading..
	int i,N,M;
	
	for(i=0; S1[i]!='\0' && i<NMAX; ++i)
	{
		A[i]=(int)S1[i]-97;
		//P1[A[i]].push_back(i);
		N=i;
	}
	
	for(i=0; S2[i]!='\0' && i<NMAX; ++i)
	{
		B[i]=(int)S2[i]-97;
		//P2[A[i]].push_back(i);
		M=i;
	}
	
	//-new game- || load game || save game || options || credits || exit
	int j,k;
	for(k=0; k<26; ++k )
		V1[k][0]=V2[k][0]=-1;
	
	for( i=0; i<=N; ++i )
	{
		V1[ A[i] ][1]=i;
		
		for(j=0; j<=M; ++j)
		{
			V2[ B[j] ][1]=j;
			
			if( A[i]==B[j] )
			{
				C[i][j]=C[i-1][j-1]+1;
			
				if( C[i][j]==1 )
					NR[i][j]=1;
				else
				{
					for( k=0; k<26; ++k )
					{
						int a1=V1[k][0],a2=V2[k][0];
						if( a1!=-1 && a2!=-1 )
						if( (C[ a1 ][ a2 ] == C[ a1-1 ][ a2-1 ]+1) && ( C[a1][a2]==C[i][j]-1 ) && a1<i && a2<j )
						{
							NR[i][j]=(NR[i][j]+NR[a1][a2])%MOD;
						}
					}
					int a=0;
				}	
			}
			else
			{
				C[i][j]=max( C[i-1][j], C[i][j-1] );
			}
			int b=9;
			
			V2[ B[j] ][0]=j;
		}
		V1[ A[i] ][0]=i;
	}
	
	int ANS=0;
	/*
	for(i=0; i<=N; ++i)
	{	for(j=0; j<=M; ++j)
			printf("%d ",NR[i][j]);
	printf("\n");
	}*/
	
	for( k=0; k<26; ++k )
	{
		int a1=V1[k][0],a2=V2[k][0];
		if( (C[ a1 ][ a2 ] == C[ a1-1 ][ a2-1 ]+1) && C[a1][a2]==C[N][M] )
				ANS=(ANS+NR[a1][a2])%MOD;
	}
	
	printf("%d\n",ANS);
	
	return 0;
}