//#define DEBUG

#include <cstdio>
#include <cstring>
#ifdef DEBUG
#include <iostream>
using namespace std;
#endif

#define NMAX 505
#define MOD 666013

int M, N;
char A[NMAX], B[NMAX];
short int lastA[26], lastB[26];
short int L[NMAX][NMAX];
int cnt[NMAX][NMAX];
int sol=0;

inline short int max(short int x, short int y)
{
	return x>y ? x : y;
}

void init()
{
	for(int i=0; i<=M; i++)
		L[i][0]=0;
	for(int i=0; i<=N; i++)
		L[0][i]=0;
	for(int i=1; i<=M; i++)
		for(int j=1; j<=N; j++)
			if(A[i]==B[j])
				L[i][j]=L[i-1][j-1]+1;
			else
				L[i][j]=max(L[i-1][j],L[i][j-1]);
}

void solve()
{
	int i, j, k;
	for(int ii=0; ii<26; ii++)
		lastA[ii]=-1;
	for(i=1; i<=M; i++)
	{
		for(int ii=0; ii<26; ii++)
			lastB[ii]=-1;
		for(j=1; j<=N; j++)
		{
			if(A[i]==B[j])
				if(L[i][j]==1)
					cnt[i][j]=1;
				else
				{
					cnt[i][j]=0;
					for(k=0; k<26; k++)
						if(lastA[k]!=-1 && lastB[k]!=-1 && L[i][j]==L[lastA[k]][lastB[k]]+1)
						{
							cnt[i][j]+=cnt[lastA[k]][lastB[k]];
							if(cnt[i][j]>=MOD)
								cnt[i][j]-=MOD;
						}
				}
			lastB[B[j]-'a']=j;
		}
		lastA[A[i]-'a']=i;
	}
}

void count_strings()
{
	for(int k=0; k<26; k++)
		if(lastA[k]!=-1 && lastB[k]!=-1 && L[lastA[k]][lastB[k]]==L[M][N])
		{
			sol+=cnt[lastA[k]][lastB[k]];
			if(sol>=MOD)
				sol-=MOD;
		}
}


int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	A[0]=B[0]='.';
	fgets(A+1,NMAX,stdin);
	fgets(B+1,NMAX,stdin);
	M=strlen(A)-2;
	N=strlen(B)-2;
#ifdef DEBUG
	cerr<<"A="<<A+1<<"\tlung="<<M<<endl;
	cerr<<"B="<<B+1<<"\tlung="<<N<<endl;
#endif
	init();
#ifdef DEBUG
	cerr<<"L="<<endl;
	for(int i=1; i<=M; i++)
	{
		for(int j=1; j<=N; j++)
			cerr<<L[i][j]<<" ";
		cerr<<endl;
	}
#endif
	solve();
#ifdef DEBUG
	cerr<<"cnt="<<endl;
	for(int i=1; i<=M; i++)
	{
		for(int j=1; j<=N; j++)
			cerr<<cnt[i][j]<<" ";
		cerr<<endl;
	}
#endif
	count_strings();
	printf("%d\n",sol);
	return 0;
}