#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int nmax=510;
const int mod=666013;
char s[2][nmax];
int prev[2][26][nmax],dyn1[nmax][nmax],lmax=0,nr[nmax][nmax];
int last[2][26][nmax];

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

void read_input()
{
	FILE *f=fopen("subsir.in","r");
	fgets(s[0],nmax,f);
	fgets(s[1],nmax,f);
	fclose(f);
}

void preproc()
{
	char c='a';
	int poz=-1,j;

	for(int inc=0;inc<2;inc++)
	{	
		for(int i=0;i<26;i++)
		{
			poz=-1;
			for(j=0;j<strlen(s[inc])-1;j++)
			{
				prev[inc][i][j]=poz;
				if(s[inc][j]==c+i)
					poz=j;
			}
			last[inc][i][j-1]=poz;
		}
	}
}

void dynamic()
{
	for(int i=0;i<nmax;i++)
	{
		dyn1[0][i]=0;
		dyn1[i][0]=0;
	}
	int len1=strlen(s[0]);
	int len2=strlen(s[1]);
	for(int i=0;i<len1-1;i++)
	{
		for(int j=0;j<len2-1;j++)
		{
			if(s[0][i]==s[1][j])
			{
				dyn1[i+1][j+1]=dyn1[i][j]+1;
				if(dyn1[i][j]==0)
					nr[i][j]=1;
			}
			else
				dyn1[i+1][j+1]=max(dyn1[i+1][j],dyn1[i][j+1]);
		}
	}
	lmax=dyn1[len1-2][len2-2];
}

int  solve()
{
	int sol=0;
	int len1=strlen(s[0]);
	int len2=strlen(s[1]);
	for(int i=0;i<len1-1;i++)
		for(int j=0;j<len2-1;j++)
		{
			if(s[0][i]==s[1][j])
			{
				for(int k=0;k<26;k++)
				{
					int ii=prev[0][k][i]+1;
					int jj=prev[1][k][j]+1;
					if(dyn1[i+1][j+1]==dyn1[ii][jj]+1)
					{
						nr[i][j]+=nr[ii-1][jj-1];
						nr[i][j]%=mod;
					}
				}
			}
		}
	
	for(int i=0;i<26;i++)
	{
		int len1=strlen(s[0])-2;
		int len2=strlen(s[1])-2;
		int ind1=last[0][i][len1];
		int ind2=last[1][i][len2];
		if(dyn1[ind1+1][ind2+1]==lmax && ind1!=-1 && ind2!=-1)
		{
			sol+=nr[ind1][ind2];
			sol%=mod;
		}
	}
	return sol;
}

void write_sol()
{
	FILE *f=fopen("subsir.out","w");
	preproc();
	dynamic();
	fprintf(f,"%i\n",solve());
	fclose(f);
}

int main()
{
	read_input();
	write_sol();
}