using namespace std;
#include<cstdio>
#include<string.h>
#define MAX_N 512
#define Mod 666013
int nr[MAX_N][MAX_N];
char A[MAX_N], B[MAX_N];
int bst[MAX_N][MAX_N];
int pi[27][MAX_N];
int pj[27][MAX_N];
int sol, N,M;
int viz[27];
inline int max(int a, int b) { return (a>b)?a:b; }
int main()
{
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	int i,j,ii,jj,c;
	scanf("%s\n",A+1);
	scanf("%s\n",B+1);
	A[0] = '!'; B[0] = '!';
	N = strlen(A) - 1; M = strlen(B) - 1;
	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j)
			if(A[i] == B[j]) bst[i][j] = bst[i-1][j-1] + 1;
			else bst[i][j] = max(bst[i-1][j], bst[i][j-1]);
	for(i=1;i<=26;++i)
	{
		pi[i][0] = pj[i][0] = -1;
		    for(j=1;j<=N;++j) 
			if(A[j] == (char)(i+96))  pi[i][j] = j; 
			else pi[i][j] = pi[i][j-1];
	    for(j=1;j<=M;++j)
			if(B[j] == (char)(i+96))  pj[i][j] = j;
			else pj[i][j] = pj[i][j-1];
	}
	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j)
			if(A[i] == B[j])
			{
				if(bst[i][j] == 1) nr[i][j] = 1;
			    for(c=1;c<=26;++c)
				{
					ii = pi[c][i-1]; // ultima aparitie a lui c in A[1..i-1]
					jj = pj[c][j-1]; // ultima aparitie a lui c in B[1...j-1]
					if(ii==-1 || jj==-1) continue;
					if(bst[i][j] == bst[ii][jj] + 1) 
						nr[i][j] = (nr[i][j] + nr[ii][jj]) % Mod;
				}
			}
	sol = 0;
	nr[0][0] = 1;
	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j)
			if(A[i] == B[j] && bst[i][j] == bst[N][M])
			{
				ii = pi[A[i]-96][N];
				jj = pj[B[j]-96][M];
				if(ii <= i && jj <= j) sol = (sol + nr[i][j]) % Mod;
			}
	printf("%d\n",sol);
	return 0;
}