#include <cstdio>
#include <cstring>
#define mod 666013
#define nmax 505
#define maxim(a,b) (a>b)?a:b
using namespace std;

int mat[nmax][nmax];
char s1[nmax],s2[nmax];
int i,j,l1,l2,maxsecv,nrmax;

int main() {
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	scanf("%s %s",s1,s2);
	l1 = strlen(s1);
	l2 = strlen(s2);
	for (i=l1;i>=1;i--) s1[i] = s1[i-1];
	for (i=l2;i>=1;i--) s2[i] = s2[i-1];
	for (i=1;i<=l2;i++) {
		for (j=1;j<=l1;j++) {
			if (s1[j] == s2[i]) mat[i][j] = mat[i-1][j-1] +1;
			maxsecv = maxim(maxsecv,mat[i][j]);
		}
	}
	for (i=1;i<=l2;i++) {
		for (j=1;j<=l1;j++) {
			if (mat[i][j] == maxsecv && mat[i][0] == 0 && mat[0][j] == 0) {
				nrmax = (nrmax +1) % mod;
				mat[i][0] = -1;
				mat[0][j] = -1;
			}
		}
	}
	printf("%d",nrmax);
	return 0;
}