#include<fstream>
#include<algorithm>
#include<cstring>

#define NMAX 505
#define get_max(a,b) ((a)>(b)?(a):(b))
#define MOD 666013

using namespace std;

ifstream f("subsir.in");
ofstream g("subsir.out");

char sir1[NMAX],sir2[NMAX];
int preda[NMAX][27],predb[NMAX][27];
int DP[NMAX][NMAX],d[NMAX][NMAX];
int len1 , len2 ;

void Preprocess ( void )
{
	int i , j ;
	for( i = 1 ; i <= len1 ; ++i )
	{
		for( j = 0 ; j < 26 ; ++j )
			preda[i][j] =  preda[ i-1][j] ;
		preda[i][sir1[i] - 'a'] = i ;
	}
	for( i = 1 ; i <= len2 ; ++i )
	{
		for( j = 0 ; j < 26 ; ++j )
			predb[i][j] =  predb[ i-1][j] ;
		predb[i][sir2[i] - 'a'] = i ;
	}

	
}
void Dynamic ( void )
{
	int i , j ;
	for( i = 1 ; i <= len1 ; ++i )
		for( j = 1 ; j <= len2 ; ++j )
			if( sir1[i] == sir2[j] )
				DP[i][j] = DP[i-1][j-1] + 1 ;
			else
				DP[i][j] = get_max( DP[i-1][j] , DP[i][j-1]  ) ;
	
}

int main ( void )
{
	sir1[0] = ' ';
	sir2[0] = ' ';
	f>>(sir1+1)>>(sir2+1);
	len1 = strlen(sir1+1);
	len2 = strlen(sir2+1);
	Preprocess();
	Dynamic();
	d[0][0] = 1 ; 
	int i , j , k , pa , pb;
	for(  i = 1 ; i <= len1 ; ++i )
		for( j = 1 ; j <= len2 ; ++j )
		{
			if(DP[i][j] == 1)
			{
				d[i][j] = 1 ;
				continue ;
			}
			for( k = 0 ; k < 26 ; ++k )
			{
				pa = preda[i-1][k] ;
				pb = predb[j-1][k] ; 
				if( DP[i][j] == DP[pa][pb] + 1 )
				{
					d[i][j] += d[pa][pb] ;
					d[i][j] %= MOD;
				}
				
			}
			
		}
	g<<d[len1][len2]<<"\n";
	f.close();
	g.close();
	return 0 ;
}