#include <cstdio>

const int MAX_SIZE(502);
const int MODULO(666013);

char a [MAX_SIZE];
char b [MAX_SIZE];
int a_size, b_size;

int length [MAX_SIZE] [MAX_SIZE];
int unique [MAX_SIZE] [MAX_SIZE];

inline void read (void)
{
	std::freopen("subsir.in","r",stdin);
	std::scanf("%s%s",a + 1,b + 1);
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("subsir.out","w",stdout);
	std::printf("%d\n",unique[a_size][b_size]);
	std::fclose(stdout);
}

inline void initialize (void)
{
	unique[0][0] = 1;
	int i;
	for (i = 1 ; a[i] ; ++i)
		unique[0][i] = 1;
	a_size = i - 1;
	for (i = 1 ; b[i] ; ++i)
		unique[i][0] = 1;
	b_size = i - 1;
}

inline void dynamic (void)
{
	int i, j;
	for (i = 1 ; i <= a_size ; ++i)
		for (j = 1 ; j <= b_size ; ++j)
			if (a[i] == b[j])
			{
				length[i][j] = length[i - 1][j - 1] + 1;
				unique[i][j] = unique[i - 1][j - 1];
			}
			else if (length[i - 1][j] == length[i][j - 1])
			{
				length[i][j] = length[i - 1][j];
				unique[i][j] = (unique[i - 1][j] + unique[i][j - 1]) % MODULO;
				if (length[i - 1][j] == length[i - 1][j - 1])
					unique[i][j] = (unique[i][j] + MODULO - unique[i - 1][j - 1]) % MODULO;
			}
			else if (length[i - 1][j] > length[i][j - 1])
			{
				length[i][j] = length[i - 1][j];
				unique[i][j] = unique[i - 1][j];
			}
			else
			{
				length[i][j] = length[i][j - 1];
				unique[i][j] = unique[i][j - 1];
			}
}

int main (void)
{
	read();
	initialize();
	dynamic();
	print();
	return 0;
}