#include <cstdio>
#include <cstring>
using namespace std;

unsigned int a[505][505],s[505][505];
int n,m,i,j;
char s1[505],s2[505];

int main() {
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s\n",s1+1);
	scanf("%s\n",s2+1);
	n = strlen(s1+1);
	m = strlen(s2+1); 
	for(i=0;i<=500;i++) {
		a[i][0] = 1;
		a[0][i] = 1;
		s[i][0] = 1;
		s[0][i] = 1;
	}
	for(i=1;i<=n;i++) for(j=1;j<=m;j++)
		if(s1[i]==s2[j]) {
			a[i][j] = a[i-1][j-1]+1;
			s[i][j] = s[i-1][j-1];
		} else if (a[i-1][j] == a[i][j-1]) {
			a[i][j] = a[i-1][j];
			s[i][j] = (s[i-1][j]+s[i][j-1]) %666013;
			if (a[i-1][j-1] == a[i-1][j]) s[i][j] = (s[i][j]-s[i-1][j-1] +666013) %666013;
        } else if (a[i-1][j] < a[i][j-1]) {
			a[i][j] = a[i][j-1];
			s[i][j] = s[i][j-1];
        } else if (a[i][j-1] < a[i-1][j]) {
			a[i][j] = a[i-1][j];
			s[i][j] = s[i-1][j];
        }
	printf("%d",s[n][m]);
	return 0;
}