#include<stdio.h>
#include<cstring>

#define maxdim 505
#define mod 666013

FILE*f=fopen("subsir.in","r");
FILE*g=fopen("subsir.out","w");

int n,m,i,j,k;
int Last1[27][maxdim],Last2[27][maxdim];
int D[maxdim][maxdim],Nr[maxdim][maxdim];
char A[maxdim],B[maxdim];

inline int max ( int a , int b ){
	return a >= b ? a : b;
}

int main () {
	
	fscanf(f,"%s\n%s",A+1,B+1);
	n = strlen(A+1); m = strlen(B+1);
	
	int last_ap;
	for ( i = 1 ; i <= 26 ; ++i ){
		last_ap = 0;
		for ( j = 1 ; j <= n + 1 ; ++j ){
			Last1[i][j] = last_ap;
			if ( A[j] == i + 'a' - 1 )
				last_ap = j;
		}
	}
	
	for ( i = 1 ; i <= 26 ; ++i ){
		last_ap = 0;
		for ( j = 1 ; j <= m + 1 ; ++j ){
			Last2[i][j] = last_ap;
			if ( B[j] == i + 'a' - 1 )
				last_ap = j;
		}
	}
	
	int longest = 0;
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			if ( A[i] == B[j] ){
				D[i][j] = 1;
				for ( k = 1 ; k <= 26 ; ++k ){
					int p1 = Last1[k][i];
					int p2 = Last2[k][j];
					
					D[i][j] = max(D[i][j],D[p1][p2]+1);
				}
				
				longest = max(longest,D[i][j]);
				
				if ( D[i][j] == 1 ){
					Nr[i][j] = 1;
				}
				else{
					for ( k = 1 ; k <= 26 ; ++k ){
						int p1 = Last1[k][i];
						int p2 = Last2[k][j];
						
						if ( D[p1][p2] == D[i][j] - 1 ){
							Nr[i][j] += Nr[p1][p2];
							if ( Nr[i][j] >= mod )
								Nr[i][j] -= mod;
						}
					}
				}
			}
		}
	}
	
	int sol = 0;
	for ( k = 1 ; k <= 26 ; ++k ){
		int p1 = Last1[k][n+1];
		int p2 = Last2[k][m+1];
		
		if ( D[p1][p2] == longest ){
			sol += Nr[p1][p2];
			if ( sol >= mod )
				sol -= mod;
		}
	}
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}