#include <stdio.h>
#include <string.h>

int vals[500][500];
int sum[500][500];
char *c1 = new char[500];
char *c2 = new char[500];


int pos1[500][26];
int pos2[500][26];

void preprocesareUltimePozitii()
{
	for (int i = 0 ; i < 26; i++)
	{
		pos1[0][i] = -1;
		pos2[0][i] = -1;
	}
	for (int i = 1 ; i < strlen(c1); i++)
	{
		for (int j = 0 ; j < 26; j++)
			pos1[i][j] = pos1[i-1][j];

		pos1[i][c1[i-1] - 'a'] = i - 1;
	}
	for (int i = 1 ; i < strlen(c2); i++)
	{
		for (int j = 0 ; j < 26; j++)
			pos2[i][j] = pos2[i-1][j];

		pos2[i][c2[i-1] - 'a'] = i - 1;
	}
}

int main()
{
	freopen ("subsir.in","r",stdin);  
	freopen ("subsir.out","w",stdout);
	scanf("%s", c1);
	scanf("%s", c2);

	int i = 0;
	int j = 0;
	int len1 = strlen(c1);
	int len2 = strlen(c2);
	
	for (i = 0 ; i < len1; i++)
	{
		for (j = 0 ; j < len2; j++)
		{
			if (c1[i] == c2[j])
			{
				if (i == 0 || j == 0)
					vals[i][j] = 1;
				else
					vals[i][j] = vals[i-1][j-1] + 1;
			}
			else
			{
				if (i != 0 && j != 0)
					if (vals[i-1][j] > vals[i][j-1])
						vals[i][j] = vals[i-1][j];
					else
						vals[i][j] = vals[i][j-1];
				else
					if (i == 0 && j > 0)
						vals[i][j] = vals[i][j-1];
					if (j == 0 && i > 0)
						vals[i][j] = vals[i-1][j];
			}
		}
	}
	
	preprocesareUltimePozitii();

	for (i = 0; i < len1; i++)
		for (j = 0 ; j < len2; j++)
		{
			if (vals[i][j] == 1 && c1[i] == c2[j])
				sum[i][j] = 1;
		}

	int p1;
	int p2;
	char c = 'a';
	for (i = 0 ; i < len1; i++)
	{
		for (j = 0 ; j < len2 ; j++)
			if (c1[i] == c2[j])
			{
				for (c = 'a'; c < 'z'; c++)
				{
					p1 = pos1[i][c - 'a'];
					p2 = pos2[j][c - 'a'];
					if (p1 == -1 || p2 == -1)
						continue;
					if (vals[p1][p2] + 1 == vals[i][j])
					{
						if (vals[p1][p2] == 1)
							sum[i][j] = 1;	
						else
							sum[i][j] = (sum[i][j] + sum[p1][p2]) % 666013;
					}
				}
			}
	}
	
	int k = 0;
	int res = 0;
	bool found = false;
	for (i = 0; i < len1; i++)
		for (j = 0 ; j < len2; j++)
		{
			if (c1[i] == c2[j])
			{
				found = false;
				for (k = i + 1; k < len1 ; k++)
					if (c1[k] == c1[i])
						found = true;
				for (k = j + 1; k < len2 ; k++)
					if (c2[k] == c2[j])
						found = true;
			}
			else
				found = false;
			
			if (!found && vals[i][j] == vals[len1 - 1][len2 - 1])
				res = (res + sum[i][j]) % 666013;
		}
	printf("%d\n", res);
	return 0;
}