//Ilie Dumitru
#include<cstdio>
#include<cstring>
const int NMAX=512;
const int MOD=666013;

int N, M;
int max[NMAX][NMAX], cnt[NMAX][NMAX];
char s[2][NMAX];
int answer=0;
int last[2][NMAX][26];

void precalc()
{
	int i, j;

	for(i=1;i<=N;++i)
	{
		for(j=0;j<26;++j)
			last[0][i][j]=last[0][i-1][j];
		last[0][i][s[0][i]-'a']=i;
	}
	for(i=1;i<=M;++i)
	{
		for(j=0;j<26;++j)
			last[1][i][j]=last[1][i-1][j];
		last[1][i][s[1][i]-'a']=i;
	}
}

void dp()
{
	int i, j;

	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j)
		{
			if(s[0][i]==s[1][j])
				max[i][j]=max[i-1][j-1]+1;
			else if(max[i-1][j]>max[i][j-1])
				max[i][j]=max[i-1][j];
			else
				max[i][j]=max[i][j-1];
		}
}

void dp0()
{
	int i, j, k;

	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j)
		{
			if(s[0][i]==s[1][j])
			{
				if(max[i][j]==1)
					cnt[i][j]=1;
				else
				{
					for(k=0;k<26;++k)
					{
						if(max[i][j]==max[last[0][i-1][k]][last[1][j-1][k]]+1)
							cnt[i][j]=(cnt[i][j]+cnt[last[0][i-1][k]][last[1][j-1][k]])%MOD;
					}
				}
				if(max[i][j]==max[N][M] && max[i][j]>max[i][last[1][j-1][s[0][i]-'a']] && max[i][j]>max[last[0][i-1][s[0][i]-'a']][j])
					answer=(answer+cnt[i][j])%MOD;
			}
		}
}

int main()
{
	FILE* f=fopen("subsir.in", "r"), *g=fopen("subsir.out", "w");
	//FILE* f=stdin, *g=stdout;

	fgets(s[0]+1, NMAX-1, f);
	fgets(s[1]+1, NMAX-1, f);

	N=strlen(s[0]+1);
	if(s[0][N]=='\n')
		s[0][N--]=0;
	M=strlen(s[1]+1);
	if(s[1][M]=='\n')
		s[1][M--]=0;

	precalc();
	dp();
	dp0();
	fprintf(g, "%d\n", answer);

	fclose(f);
	fclose(g);
	return 0;
}