#include<fstream>
#include<cstring>
using namespace std;
char s1[505],s2[505];
long l[505][505],nr[505][505],n,m;
void creare()
{
	int i,j;
	for(i=0;i<=m;i++)
		nr[0][i]=1;
	for(i=0;i<=n;i++)
		nr[i][0]=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				l[i][j]=l[i-1][j-1]+1;
				nr[i][j]=nr[i-1][j-1];
			}
			else
			{
				if(l[i-1][j]==l[i][j-1])
				{
					l[i][j]=l[i-1][j];
					nr[i][j]=nr[i-1][j]+nr[i][j-1];
					if(l[i-1][j-1]==l[i-1][j])
						nr[i][j]=nr[i][j]-nr[i-1][j-1];
				}
				else
					if(l[i-1][j]>l[i][j-1])
						{
							l[i][j]=l[i-1][j];
							nr[i][j]=nr[i-1][j];
					}
					else {
						l[i][j]=l[i][j-1];
						nr[i][j]=nr[i][j-1];
					}
			}
		}
}
int main()
{
	ifstream fin("subsir.in");
	ofstream fout("subsir.out");
	fin.getline(s1,505);
	fin.getline(s2,505);
	n=strlen(s1);
	m=strlen(s2);
	creare();
	fout<<nr[n][m]%666013;
	return 0;
}