#include <algorithm>
#include <stdio.h>

#define MAX 512
#define restRez 666013

using namespace std;

int prec1[MAX][32], prec2[MAX][32];
int lung[MAX][MAX], pos[MAX][MAX];
char str1[MAX], str2[MAX];

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

	fgets(str1 + 1, MAX, stdin);
	int n = strlen(str1 + 1) - 1;
	fgets(str2 + 1, MAX, stdin);
	int m = strlen(str2 + 1) - 1;

	for (int i = 1; i <= n + 1; i++)
	{
		memcpy(prec1[i], prec1[i - 1], sizeof(prec1[i]));

		prec1[i][str1[i - 1] - 'a'] = i - 1;
	}

	for (int i = 1; i <= m + 1; i++)
	{
		memcpy(prec2[i], prec2[i - 1], sizeof(prec2[i]));

		prec2[i][str2[i - 1] - 'a'] =  i - 1;
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (str1[i] == str2[j])
				lung[i][j] = lung[i - 1][j - 1] + 1;
			else lung[i][j] = max(lung[i - 1][j], lung[i][j - 1]);

			if (lung[i][j] == 1)
				pos[i][j] = 1;
			else for (int cf = 0; cf < 26; cf++)
				if (lung[prec1[i][cf]][prec2[j][cf]] == lung[i][j] - 1)
					pos[i][j] = (pos[i][j] + pos[prec1[i][cf]][prec2[j][cf]]) % restRez;
		}

	for (int cf = 0; cf < 26; cf++)
		if (lung[prec1[n + 1][cf]][prec2[m + 1][cf]] == lung[n][m])
			pos[n + 1][m + 1] = (pos[n + 1][m + 1] + pos[prec1[n + 1][cf]][prec2[m + 1][cf]]) % restRez;

	printf("%d\n", pos[n + 1][m + 1]);

	fclose(stdin);
	fclose(stdout);
	return 0;
}