#include<cstdio>
#define MOD 666013
#define adun(a,b) (((a+=b)>=MOD)? (a-=MOD): (0))
#define maxim(a,b) (a>b?a:b)
#define N 505
#define INF 1000000
char s[2][N];
int p[2][30][N],nr[N][N],lung1,lung0,rez,lung[N][N];
void citire()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	fgets(s[0]+1,N,stdin);
	fgets(s[1]+1,N,stdin);
	//aflu lungimea celui mai mare subsir comun
	for (int i=1; s[0][i]&&s[0][i]!='\n'; ++i)
	{
		++lung0;
		for (int j=1; s[1][j]&&s[1][j]!='\n'; ++j)
		{
			if(i==1)
				++lung1;
			if (s[0][i]==s[1][j])
				lung[i][j]=lung[i-1][j-1]+1;
			else
				lung[i][j]=maxim(lung[i-1][j],lung[i][j-1]);
		}
	}
	//aflu poz cea mai din dreapta a caracterului c pana intr-o poz data
	for(int k=0; k<=1; ++k)
		for (char c='a'; c<='z'; ++c)
		{
			p[k][c][0]=INF;
			for (int i=1; s[k][i]&&s[k][i]!='\n'; ++i)
				for (int c='a'; c<='z'; ++c)
					if (s[k][i]==c)
						p[k][c][i]=i;
					else
						p[k][c][i]=p[k][c][i-1];
		}
	//numaratoare
	for (int i=1; s[0][i]&&s[0][i]!='\n'; ++i)
		for (int j=1; s[1][j]&&s[1][j]!='\n'; ++j)
		{
			if (s[0][i]!=s[1][j])
				continue;
			if (lung[i][j]==1)
			{
				nr[i][j]=1;
				continue;
			}
			for (char c='a'; c<='z'; ++c)
			{
				int ii=p[0][c][i-1],jj=p[1][c][j-1];
				if (ii<i&&jj<j&&lung[ii][jj]+1==lung[i][j])
					adun(nr[i][j],nr[ii][jj]);
			}
		}
	//calculez rezulttul final
	for (char c='a'; c<='z'; ++c)
	{
		int ii=p[0][c][lung0],jj=p[1][c][lung1];
		if(ii<=lung0&&jj<=lung1&&lung[ii][jj]==lung[lung0][lung1])
			adun(rez,nr[ii][jj]);
	}		
	printf("%d\n",rez);
}
int main()
{
	citire();
	return 0;
}