#include <cstdio>
#include <cstring>

#define NMAX 505
#define MOD 66013

int M,N;
char a[NMAX], b[NMAX];
short int L[NMAX][NMAX][26]; int cnt[NMAX][NMAX][26];
short int maxL[NMAX][NMAX]; int sumcnt[NMAX][NMAX];

int solve()
{
	int i,j,k;
	// initializari
	for(i=0; i<=M; i++)
		for(k=0; k<26; k++)
		{
			L[i][0][k]=0;
			cnt[i][0][k]=1;
			maxL[i][0]=0;
			sumcnt[i][0]=1;
		}
	for(j=0; j<=N; j++)
		for(k=0; k<26; k++)
		{
			L[0][j][k]=0;
			cnt[0][j][k]=1;
			maxL[0][j]=0;
			sumcnt[0][j]=1;
		}
	// rezolvare
	for(i=1; i<=M; i++)
		for(j=1; j<=N; j++)
		{
			maxL[i][j]=0;
			sumcnt[i][j]=1;
			for(k=0; k<26; k++)
			{
				if(a[i]==k+'a')
					if(b[j]==k+'a')
					{
						L[i][j][k]=maxL[i-1][j-1]+1;
						cnt[i][j][k]=sumcnt[i-1][j-1];
						if(L[i][j][k]==L[i-1][j][k])
						{
							cnt[i][j][k]+=cnt[i-1][j][k];
							if(cnt[i][j][k]>=MOD)
								cnt[i][j][k]-=MOD;
						}
						if(L[i][j][k]==L[i][j-1][k])
						{
							cnt[i][j][k]+=cnt[i][j-1][k];
							if(cnt[i][j][k]>=MOD)
								cnt[i][j][k]-=MOD;
						}
					}
					else
					{
						L[i][j][k]=L[i][j-1][k];
						cnt[i][j][k]=cnt[i][j-1][k];
					}
				else
					if(b[j]==k+'a')
					{
						L[i][j][k]=L[i-1][j][k];
						cnt[i][j][k]=cnt[i-1][j][k];
					}
					else
					{
						L[i][j][k]=L[i-1][j-1][k];
						cnt[i][j][k]=cnt[i-1][j-1][k];
					}
				if(maxL[i][j]==L[i][j][k])
				{
					if(maxL[i][j])
					{
						sumcnt[i][j]+=cnt[i][j][k];
						if(sumcnt[i][j]>=MOD)
							sumcnt[i][j]-=MOD;
					}
				}
				else
					if(maxL[i][j]<L[i][j][k])
					{
						maxL[i][j]=L[i][j][k];
						sumcnt[i][j]=cnt[i][j][k];
					}
			}
		}
	// solutia
	return sumcnt[M][N];
}


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;
	printf("%d\n",solve());
	return 0;
}