#include <fstream>
using namespace std;
#define mod 666013
char a[505], b[505],c;
int best[505][505], nr[505][505];
int uza[30][505], uzb[30][505]; 
int main()
{
	ifstream fin("subsir.in");
	ofstream fout("subsir.out");
	
	int n=0, m=0,i,j;
	
	while((c=fin.get()) && (c!='\n'))
		a[++n]=c;
	while((c=fin.get()) && (c!=EOF))
		b[++m]=c;
	
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		{
			if(a[i]==b[j])
				best[i][j]=best[i-1][j-1]+1;
			else
				best[i][j]=max(best[i-1][j],best[i][j-1]);
			if(best[i][j]==1 && a[i]==b[j])
				nr[i][j]=1;
		}
		
	for(i=1;i<=n;++i)
		for(j='a';j<='z';++j)
			if(a[i]==j)
				uza[j-'a'][i]=i;
			else
				uza[j-'a'][i]=uza[j-'a'][i-1];
			
	for(i=1;i<=m;++i)
		for(j='a';j<='z';++j)
			if(b[i]==j)
				uzb[j-'a'][i]=i;
			else
				uzb[j-'a'][i]=uzb[j-'a'][i-1];
			
			int sol=0;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			if(a[i]==b[j])
			{
				for(int k='a';k<='z';++k)
				{
					int x=uza[k-'a'][i-1];
					int y=uzb[k-'a'][j-1];
					if(best[x][y]+1==best[i][j])
						nr[i][j]=(nr[i][j]+nr[x][y])%mod;
				}
				if(best[i][j]==best[n][m] && uza[a[i]-'a'][n]==i && uzb[b[j]-'a'][m]==j)
					sol=(sol+nr[i][j])%mod;
			}

			fout<<sol;	
		
	return 0;
}