using namespace std;

#include <cstdio>
#include <algorithm>
#include <vector>

#define IN "subsir.in"
#define OUT "subsir.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<9
#define MOD 666013
#define abc 1<<8
#define si short int

char A[N_MAX],B[N_MAX];
si C[N_MAX][N_MAX],MA[abc][N_MAX],MB[abc][N_MAX];
int NR[N_MAX][N_MAX];
int N,M;

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	fgets(A+1,1<<10,stdin);
	fgets(B+1,1<<10,stdin);
	N = strlen(A+1)-1;
	M = strlen(B+1);
	if(B[M] == '\n')
		--M;
}

void solve()
{
	int rez(0);
	FOR(i,1,N)
	FOR(j,1,M)
		C[i][j] = (A[i] == B[j] ? C[i-1][j-1] + 1 : max(C[i-1][j],C[i][j-1]) );
			
	FOR(l,'a','z')
	FOR(i,1,N)
		MA[l][i] = (A[i] == l ? i : MA[l][i-1]);
		
	FOR(l,'a','z')
	FOR(i,1,M)
		MB[l][i] = (B[i] == l ? i : MB[l][i-1]);
		
	FOR(i,1,N)
	FOR(j,1,M)
		if(A[i] == B[j])
		{
			bool ok(false);
			FOR(l,'a','z')
				if(MA[l][i-1] && MB[l][j-1])
					{
						int ii = MA[l][i-1];
						int jj = MB[l][j-1];
						ok = true;
						if( C[i][j] == C[ii][jj] + 1) 
							NR[i][j] += NR[ii][jj],
							NR[i][j] %= MOD;
					}
			if(!ok) 
				NR[i][j] = 1;
		}	
	
	FOR(i,1,N)
	FOR(j,1,M)
		if(A[i] == B[j] && C[i][j] == C[N][M])
		{
			bool ok(true);
			FOR(k,i+1,N)
				if(A[k] == A[i]) 
					ok = false;
			FOR(k,j+1,M)
				if(B[k] == A[i]) 
					ok = false;
			if(ok) 
				rez += NR[i][j],
				rez %= MOD;
		}
	printf("%d\n", rez);	
}

int main()
{
	scan();
	solve();
	return 0;
}