#include <fstream>

using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

char s1[512] , s2[512] , z[512];
int D[512][512] , n , m ,nrs;

void count(int lin, int col,int k) 
{
	if(k==0)
	{
	++nrs;
	return;
	}
	int	i=lin;
	while(i>0 && D[i][col]==k)
	{
	int	j=col;
	while(j>0 && D[i][j]==k)
		{
			while(j>0 && D[i][j]==k && (s1[j-1]!=s2[i-1]||(D[i-1][j-1]!=(k-1))))
			j--;
			if(j>0 && D[i][j]==k && D[i-1][j-1]==(k-1) && s1[j-1]==s2[i-1])
			{
			z[k-1]=s1[i-1]; 
			count(i-1,j-1,k-1);
			}
		j--;
		}
	i--;
	}
}

static inline int max(int a,int b)
{
	return a > b ? a : b;
}

void lcs()
{
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			s1[i-1]==s2[j-1] ? D[i][j] = D[i-1][j-1] + 1 : D[i][j] = max(D[i-1][j],D[i][j-1]);
}

int main()
{
	fin>>s1>>s2;
	n = strlen(s1) , m = strlen(s2);
	lcs();
	count(n,m,D[n][m]);
	fout<<nrs%666013;
	return 0;
}