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

#define NMax 505
#define Mod 666013

using namespace std;

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

void Initialize ()
{
    for (int i=0; i<=N; ++i) NS[i][0]=1;
    for (int i=0; i<=M; ++i) NS[0][i]=1;
}

void Solve ()
{
    Initialize ();
	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[i][j]=NS[i-1][j-1];
				continue;
			}
			if (DP[i][j-1]<DP[i-1][j])
			{
			    DP[i][j]=DP[i-1][j];
			    NS[i][j]=NS[i-1][j];
			    continue;
			}
			if (DP[i-1][j]<DP[i][j-1])
			{
			    DP[i][j]=DP[i][j-1];
			    NS[i][j]=NS[i][j-1];
			    continue;
			}
			DP[i][j]=DP[i-1][j];
			NS[i][j]=(NS[i-1][j]+NS[i][j-1])%Mod;
			if (DP[i-1][j-1]==DP[i-1][j])
			{
			    NS[i][j]=(NS[i][j]-NS[i-1][j-1]+Mod)%Mod;
			}
		}
	}
}

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", NS[N][M]);
}

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