#include "stdio.h"
#include "string.h"

#define DIMENSION 510
#define MOD 666013

FILE *f, *g;
char a[DIMENSION], b[DIMENSION];
int length[DIMENSION][DIMENSION];
int nr[DIMENSION][DIMENSION];
int N, M;

int main()
{
	f = fopen("subsir.in", "r");
	g = fopen("subsir.out", "w");

	fgets(a + 1, DIMENSION, f);
	fgets(b + 1, DIMENSION, f);

	N = strlen(a+1) - 1;
	M = strlen(b+1) - 1;

	for(int i = 0; i <= N; i++)
		nr[i][0] = 1;

	for(int i = 0; i <= M; i++)
		nr[0][i] = 1;

	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= M; j++)
		{
			if(a[i] == b[j])
			{
				length[i][j] = length[i-1][j-1];
				nr[i][j] = nr[i-1][j-1];
			}
			else if(length[i-1][j] > length[i][j-1])
			{
				length[i][j] = length[i-1][j];
				nr[i][j] = nr[i-1][j];
			}
			else if(length[i][j-1] > length[i-1][j])
			{
				length[i][j] = length[i][j-1];
				nr[i][j] = nr[i][j-1];
			}
			else 
			{
				length[i][j] = length[i][j-1];
				nr[i][j] = (nr[i-1][j] + nr[i][j-1]) % MOD;
				if(length[i][j] == length[i-1][j-1])
					nr[i][j] = (nr[i][j] - nr[i-1][j-1] + MOD) % MOD;
			}
		}

	fprintf(g, "%d", nr[N][M]);

	fclose(f);
	fclose(g);

	return 0;
}