#include <cstdio>
#include <cstring>
#define mod 666013
#define N 512

int n, m;
char a[N], b[N];
int dp[N][N], nr[N][N];

void solve ()
{
	scanf ("%s", a + 1);
	n = strlen (a + 1);
	scanf ("%s", b + 1);
	m = strlen (b + 1);

	//printf ("%s %s\n", a + 1, b + 1);
	int i, j;

	for (i = 0; i <= n; ++i)
		nr[i][0] = 1;

	for (j = 0; j <= m; ++j)
		nr[0][j] = 1;

	for (i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
		{
			if (a[i] == b[j])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
				nr[i][j] = nr[i - 1][j - 1];
			}
			else
			if (dp[i - 1][j] > dp[i][j - 1])
			{
				dp[i][j] = dp[i - 1][j];
				nr[i][j] = nr[i - 1][j];
			}
			else
			if (dp[i][j - 1] > dp[i - 1][j])
			{
				dp[i][j] = dp[i][j - 1];
				nr[i][j] = nr[i][j - 1];
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
				nr[i][j] = (nr[i][j - 1] + nr[i - 1][j]) % mod;

				if (dp[i - 1][j - 1] == dp[i - 1][j])
					nr[i][j] = ((nr[i][j] - nr[i - 1][j - 1])  + mod ) % mod;
			}
		}

	printf ("%d\n", nr[n][m]);
	
}



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

	solve ();
	return 0;
}