#include <cstdio>
#include <cstring>
#include <algorithm>

#define NMax 505
#define Mod 666013

using namespace std;

int N, M, DP[NMax][NMax], NS[NMax][256];
char String[2][NMax];

inline int Sum (int L)
{
	int S=0;
	for (int i='a'; i<='z'; ++i) S=(S+NS[L][i])%Mod;
	return S;
}

void Solve ()
{
	NS[0]['a']=1;
	for (int i=1; i<=N; ++i)
	{
		for (int j=1; j<=M; ++j)
		{
			if (String[0][i]==String[1][j])
			{
				DP[i][j]=1+DP[i-1][j-1];
				NS[DP[i][j]][String[0][i]]=Sum (DP[i][j]-1);
			}
			else
			{
				DP[i][j]=max (DP[i-1][j], DP[i][j-1]);
			}
		}
	}
}

void Read ()
{
	freopen ("subsir.in", "r", stdin);
	scanf ("%s\n%s", String[0]+1, String[1]+1);
	N=strlen (String[0]+1); M=strlen (String[1]+1);
}

void Print ()
{
	freopen ("subsir.out", "w", stdout);
	printf ("%d\n", Sum (DP[N][M]));
}

int main ()
{
	Read ();
	Solve ();
	Print ();
	return 0;
}