#include<stdio.h>
#include<string.h>
#define NMAX 512
#define MOD 666013

int N, M, i, j, D[NMAX][NMAX], Nr[NMAX][NMAX];
char A[NMAX], B[NMAX];

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);

	scanf("%s\n", A+1); N = strlen(A+1);
	scanf("%s\n", B+1); M = strlen(B+1);

	for( i=0; i<=N; i++ ) Nr[i][0] = 1;
	for( j=0; j<=M; j++ ) Nr[0][j] = 1;

	for( i=1; i<=N; i++ )
		for( j=1; j<=M; j++ )
		{
			if( A[i] == B[j] )
			{
				D[i][j] = D[i-1][j-1] + 1;
				Nr[i][j] = Nr[i-1][j-1];
			}
			else if( D[i-1][j] == D[i][j-1] )
			{
				D[i][j] = D[i-1][j];
				Nr[i][j] = ( Nr[i-1][j] + Nr[i][j-1] ) % MOD;

				if( D[i-1][j] == D[i-1][j-1] )
					Nr[i][j] = ( Nr[i][j] - Nr[i-1][j-1] + MOD ) % MOD;
			}
			else if( D[i-1][j] > D[i][j-1] )
			{
				D[i][j] = D[i-1][j];
				Nr[i][j] = Nr[i-1][j];
			}
			else if( D[i][j-1] > D[i-1][j] )
			{
				D[i][j] = D[i][j-1];
				Nr[i][j] = Nr[i][j-1];
			}
		}

	printf("%d\n", Nr[N][M]);				

	return 0;
}