#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(x,y) ((x>y)?(x):(y))
#define mode 666013

int dp[505][505],l1,l2,bcc=0;
char s1[505],s2[505],out[505],visit[505][505];

struct tree {
	struct tree *t[26];
}
*root,*m[6561];

typedef struct L {
	int i,j;
	struct L *next;
}
linkedList;

void treecpy(struct tree *dest, struct tree *orig) {
	int i;
	for (i=0; i<26; i++) {
		if (orig->t[i]!=NULL) {
			dest->t[i] =(tree *) malloc(sizeof(struct tree));
			treecpy(dest->t[i],orig->t[i]);
		}
		else
		    dest->t[i] = NULL;
	}
}

void construct(int i, int j, struct tree *t) {
	int k;
	linkedList *q,*tail,*temp;
	if (!dp[i][j])
		return;
	temp = q = tail =(linkedList*) malloc(sizeof(linkedList));
	q->next = NULL;
	q->i = i;
	q->j = j;
	while(q!=NULL) {
		if (s1[q->i] == s2[q->j]) {
			int ind = s1[q->i]-'a';
			if (t->t[ind] == NULL) {
				t->t[ind] =(tree *) malloc(sizeof(struct tree));
				if (m[q->i*(l2+1)+q->j]!=NULL)
					treecpy(t->t[ind],m[q->i*(l2+1)+q->j]);
				else {
					for (k=0; k<26; k++)
						t->t[ind]->t[k] = NULL;
					construct(q->i+1,q->j+1,t->t[ind]);
					m[q->i*(l2+1)+q->j] = t->t[ind]; /* memorize subtree */
				}
			}
		}
		else {
			if (dp[q->i+1][q->j] == dp[q->i][q->j] && !visit[q->i+1][q->j]) {
				tail->next =(linkedList *) malloc(sizeof(linkedList));
				tail = tail->next;
				tail->next = NULL;
				tail->i = q->i+1;
				tail->j = q->j;
				visit[q->i+1][q->j] = 1;
			}
			if (dp[q->i][q->j+1] == dp[q->i][q->j] && !visit[q->i][q->j+1]) {
				tail->next =(linkedList *) malloc(sizeof(linkedList));
				tail = tail->next;
				tail->next = NULL;
				tail->i = q->i;
				tail->j = q->j+1;
				visit[q->i][q->j+1] = 1;
			}
		}
		q = q->next;
	}
	while(temp!=NULL) {
		q = temp;
		temp = temp->next;
		visit[q->i][q->j] = 0;
		free(q);
	}
}

void printanddelete(struct tree *p, int len) {
	int i;
	if (len == dp[0][0])
	    {	bcc++;  bcc%=mode; }
	else
	    for (i=0; i<26; i++) {
		out[len] = i+'a';
		if (p->t[i]!=NULL)
			printanddelete(p->t[i],len+1);
	}
	free(p);
}

int main() {
	int i,j;
	freopen("subsir.in","r",stdin);
	freopen("subsir.out","w",stdout);
	char c;
	i=0;
	scanf("%c",&c);
	do
	 {
	   s1[i]=c; i++;
	   scanf("%c",&c);
	 }
	 while (c>='a' && c<='z');
	l1=i; scanf("\n");
	i=0;
	scanf("%c",&c);
	do
	 {
	   s2[i]=c; i++;
	   scanf("%c",&c);
	 }
	while (c>='a' && c<='z');
	l2=i;

	for (i=0; i<=l1; i++)
		dp[i][l2] = 0;
	for (j=0; j<=l2; j++)
		dp[l1][j] = 0;
	for (i=l1-1; i>=0; --i)
		for (j=l2-1; j>=0; --j) {
			if (s1[i] == s2[j])
				dp[i][j] = dp[i+1][j+1]+1;
			else
				dp[i][j] = max(dp[i][j+1],dp[i+1][j]);
		}
	root =(tree *) malloc(sizeof(struct tree));
	for (i=0; i<26; i++)
		root->t[i] = NULL;
	out[dp[0][0]] = 0;
	construct(0,0,root);
	printanddelete(root,0);
	printf("%d\n",bcc);
	return 0;
}