#include <stdio.h>
#include <string.h>
#define modul 666013


char line[512], a[512],  b[512];
int n, m, c[512][512], nr[512][512], pa[27][512], pb[26][512], sol;

int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	int i, j, ii, jj, l;

	gets(line);
	for(i = 0; i < strlen(line); ++i)
	{
		if(line[i] >= 'a' && line[i] <= 'z')
			a[++n] = line[i];
	}

	gets(line);
	for(i = 0; i < strlen(line); ++i)
	{
		if(line[i]  >= 'a' && line[i] <= 'z')
			b[++m] = line[i];
	}

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= 26; ++j)
		{
			pa[j][i] = pa[j][i - 1];
		}
		pa[a[i] - 'a' + 1][i] = i;
	}
	for(i = 1; i <= m; ++i)
	{
		for(j = 1; j <= 26; ++j)
		{
			pb[j][i] = pb[j][i - 1];
		}
		pb[b[i] - 'a' + 1][i] = i;
	}
	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			if(a[i] == b[j])
				c[i][j] = c[i - 1][j - 1] + 1;
			else
			{
				if(c[i][j - 1] > c[i - 1][j])
					c[i][j] = c[i][j - 1];
				else
					c[i][j] = c[i - 1][j];
			}
		}
	}
	nr[0][0] = 1;

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			if(a[i] == b[j])
			{
				for(l = 1; l <= 26; ++l)
				{
					ii = pa[l][i - 1];
					jj = pb[l][j - 1];
					if(c[i][j] == 1)
					{
						nr[i][j] = 1; 
					}
					else
					{
						if(c[i][j] == c[ii][jj] + 1)
						{
							nr[i][j] += nr[ii][jj];
							nr[i][j] %= modul;
						}
					}
					if(c[ii][jj] == c[n][m])
						nr[ii][jj] = 0;
					if(c[ii][j] == c[n][m])
						nr[ii][j] = 0;
					if(c[i][jj] == c[n][m])
						nr[i][jj] = 0;
				}
			}
		}
	}

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			if(c[i][j] == c[n][m] && a[i] == b[j])
				sol += nr[i][j] % modul;
		}
	}

	printf("%d", sol);

	return 0;
}