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

#define MAX 512
#define restRez 666013

using namespace std;

int linPrec[MAX], linAct[MAX];
int linPrecPos[MAX][26], linActPos[MAX][26];
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 += linPrecPos[j - 1][k];

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

			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 += linActPos[m][k];

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