#include <stdio.h>
#include <string.h>
#define NMAX 510
#define MOD 666013

char A[NMAX], B[NMAX];
int C[NMAX][NMAX], nextA[NMAX][27], nextB[NMAX][27], rez[NMAX][NMAX];
int n, m, len;

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

void lcs()
{
    int i, j, k;
    for (i=1; i<=n; ++i)
	for (j=1; j<=m; ++j) {
	    if (A[i] == B[j]) 
		C[i][j] = C[i-1][j-1] + 1;
	    else 
		C[i][j] = max(C[i][j-1], C[i-1][j]);
	    len = max(len, C[i][j]);
	}
    char c;
    for (i=1; i<=n; ++i) 
	for (c='a'; c<='z'; ++c) {
	    for (k=i; A[k] != c && k<=n; ++k);
	    nextA[i][c-97] = (k == n+1 ? 0:k);
	}
    for (i=1; i<=m; ++i)
	for (c='a'; c<='z'; ++c) {
	    for (k=i; B[k] != c && k<=m; ++k); 
	    nextB[i][c-97] = (k == m+1 ? 0:k);
	}

    for (i=n; i>=1; --i)
	for (j=m; j>=1; --j) {
	    if (A[i] == B[j]) {
		if (C[i][j] == len) {
		    rez[i][j] = 1;
		    continue;
		}
		else
		    for (c='a'; c<='z'; ++c) {
			int k = nextA[i+1][c-97];
			int l = nextB[j+1][c-97];
			if (k && l && C[k][l] == C[i][j]+1) {
			    rez[i][j] += rez[k][l];
			    if (rez[i][j] >= MOD) 
				rez[i][j] -= MOD;
			}
		    }
	    }
	}
}

void print()
{
    int result = 0, i, j;
    char c;
    for (c='a'; c<='z'; ++c) {
	i = nextA[1][c-97];
	j = nextB[1][c-97];
	if (i && j && C[i][j] == 1) 
	    result += rez[i][j];
	if (result >= MOD)
	    result -= MOD;
    }
    printf("%d", result);
}
	    

int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
    int i;
    scanf("%s", A); scanf("%s", B);
    n = strlen(A); m = strlen(B);
    for (i=n; i>=1; --i)
	A[i] = A[i-1];
    for (i=m; i>=1; --i)
	B[i] = B[i-1];
    lcs();
    print();
    return 0;
}