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

#define MAX 1024
#define restRez 666013

using namespace std;

int linPrec[MAX], linAct[MAX];
int linPrecPos[MAX][28], linActPos[MAX][28];
char strPrin[MAX], strSec[MAX];

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

	fgets(strPrin + 1, MAX, stdin);
	fgets(strSec + 1, MAX, stdin);

	int n = strlen(strPrin + 1) - 1;
	int m = strlen(strSec + 1) - 1;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			linPrec[j] = linAct[j];
			linAct[j] = 0;

			for (int k = 0; k < 26; k++)
			{
				linPrecPos[j][k] = linActPos[j][k];
				linActPos[j][k] = 0;
			}
		}

		for (int j = 1; j <= m; j++)
		{
			if (strPrin[i] == strSec[j])
			{
				int suma = 0;
				for (int k = 0; k < 26; k++)
					suma = (suma + linPrecPos[j - 1][k]) % restRez;

				linAct[j] = linPrec[j - 1] + 1;
				if (linAct[j] == 1)
					linActPos[j][strPrin[i] - 'a'] = 1;
				else linActPos[j][strPrin[i] - 'a'] = suma;
			}

			linAct[j] = max(linAct[j], max(linAct[j - 1], linPrec[j]));
			if (linAct[j] == linPrec[j])
				for (int k = 0; k < 26; k++)
					linActPos[j][k] = max(linActPos[j][k], linPrecPos[j][k]);
			if (linAct[j] == linAct[j - 1])
				for (int k = 0; k < 26; k++)
					linActPos[j][k] = max(linActPos[j][k], linActPos[j - 1][k]);
		}
	}

	int sol = 0;
	for (int k = 0; k < 26; k++)
		sol = (sol + linActPos[m][k]) % restRez;

	printf("%d\n", sol);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}