#include <fstream>
using namespace std;

ifstream F("subsir.in");
ofstream G("subsir.out");	

#define Lmax 513
#define Sigma 30
#define Mod 666013

#define max(a, b) ( ( a>b ) ? a : b )
#define min(a, b) ( ( a<b ) ? a : b )

int N,M;
char A[Lmax],B[Lmax];

int Best[Lmax][Lmax];
int Nbr[Lmax][Lmax];
int LastA[Sigma][Lmax];
int LastB[Sigma][Lmax];

int sol;

void read()
{
	char c;
	while( ( c=F.get() ) && ( c!='\n' ) )
		A[++N]=c;
	while( ( c=F.get() ) && ( c!=EOF ) )
		B[++M]=c;
}

void build_Best()
{
	for (int i=1;i<=N;++i)
	for (int j=1;j<=M;++j)
	{
		Best[i][j]= ( A[i]==B[j] ) ? Best[i-1][j-1]+1 : max( Best[i-1][j] , Best[i][j-1] ) ;
		if ( Best[i][j]==1 && A[i]==B[j] )
			Nbr[i][j]=1;
	}
}

void make_LastA()
{
	for (int i=1;i<=N;++i)
	for (int j='a';j<='z';++j)
		LastA[j-'a'][i]=(A[i]==j) ? i : LastA[j-'a'][i-1] ;
}

void make_LastB()
{
	for (int i=1;i<=M;++i)
	for (int j='a';j<='z';++j)
		LastB[j-'a'][i]=(B[i]==j) ? i : LastB[j-'a'][i-1] ;
}

void make_sol()
{
	for(register int i=1;i<=N;++i)
	for(register int j=1;j<=M;++j)
	if(A[i]==B[j])
	{
		for(int k='a';k<='z';++k)
		{
			int x=LastA[k-'a'][i-1],
				y=LastB[k-'a'][j-1];
			
			if ( Best[x][y]+1==Best[i][j] )
				Nbr[i][j]=( Nbr[x][y]+Nbr[i][j] ) % Mod;
		}
		if (Best[i][j]==Best[N][M] && LastA[A[i]-'a'][N]==i && LastB[B[j]-'a'][M]==j)
			sol=( Nbr[i][j] + sol ) %Mod;
	}
}
	
int main()
{	
	read();
	build_Best();
	
	make_LastA();
	make_LastB();
	make_sol();
	
	G<<sol<<'\n';
	
	F.close();
	G.close();
	
	return 0;
}