#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NMAX 505
#define SGM 27
#define MOD 666013
#define maxim(a, b) (a > b ? a : b)
char a[NMAX], b[NMAX];
int f1[SGM], f2[SGM];
int v[NMAX][NMAX], nr[NMAX][NMAX];
int n, m;
int main(){
	int i, j, k;
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);
	scanf("%s%s", a+1, b+1);
	n = strlen(a+1);
	m = strlen(b+1);
	for(i = 1; i <= n; ++i){
		memset(f2, 0, sizeof(f2));
		for(j = 1; j <= m; ++j){
			if(a[i] == b[j]) {
				v[i][j] = v[i-1][j-1] + 1;
				if(v[i][j] == 1) nr[i][j] = 1;
				else for(k = 0; k <= 'z' - 'a'; ++k)
					if(f1[k] && f2[k])
						if(v[ f1[k] ][ f2[k] ] +1 == v[i][j])
							nr[i][j] = (nr[i][j] + nr[ f1[k] ][ f2[k] ])%MOD;
			}
			else if(v[i-1][j]>v[i][j-1]){
				v[i][j] = v[i-1][j];
				nr[i][j] = nr[i-1][j];
			}
			else if(v[i-1][j]==v[i][j-1]){
				v[i][j] = v[i-1][j];
				if(nr[i-1][j]>nr[i][j-1]) nr[i][j] = nr[i-1][j];
				else nr[i][j] = nr[i][j-1];
			}
			else {
				v[i][j] = v[i][j-1];
				nr[i][j] = nr[i][j-1];
			}
			f2[b[j] - 'a'] = j;
		}
		f1[a[i] - 'a'] = i;
	}
	printf("%d\n", nr[n][m]);
	return 0;
}