#include<fstream>
#include<cstring>
#define MOD 666013
using namespace std;
int n,m,best[510][510],nr[510][510],pred[2][26][510],sol;
char A[510],B[510];

inline void Citire()
{
	ifstream fin("subsir.in");
	fin>>(A+1); n=strlen(A+1);
	fin>>(B+1); m=strlen(B+1);
	fin.close();
}

inline void Cmlsc()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			best[i][j]=max(best[i-1][j],best[i][j-1]);
			if(A[i]==B[j])
			{
				best[i][j]=best[i-1][j-1]+1;
				if(best[i][j]==1)
					nr[i][j]=1;
			}
		}
	}
}

inline void CountCmlsc()
{
	int i,j,c,ii,jj;
	for(i=1;i<=n;i++)
	{
		for(c=0;c<26;c++)
		{
			if(A[i]==c+'a')
				pred[0][c][i]=i;
			else
				pred[0][c][i]=pred[0][c][i-1];
		}
	}
	for(i=1;i<=m;i++)
	{
		for(c=0;c<26;c++)
		{
			if(B[i]==c+'a')
				pred[1][c][i]=i;
			else
				pred[1][c][i]=pred[1][c][i-1];
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(A[i]==B[j])
			{
				for(c=0;c<26;c++)
				{
					ii=pred[0][c][i-1];
					jj=pred[1][c][j-1];
					if(best[i][j]==best[ii][jj]+1)
					{
						nr[i][j]+=nr[ii][jj];
						if(nr[i][j]>=MOD)
							nr[i][j]-=MOD;
					}
				}
				if(best[n][m]==best[i][j] && i==pred[0][A[i]-'a'][n] && j==pred[1][B[j]-'a'][m])
				{
					sol+=nr[i][j];
					if(sol>=MOD)
						sol-=MOD;
				}
			}
		}
	}
}

inline void Afisare()
{
	ofstream fout("subsir.out");
	fout<<sol<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Cmlsc();
	CountCmlsc();
	Afisare();
	return 0;
}