#include<stdio.h>
#include<string.h>
#define N 504

char a[N], b[N];
int sol[N][N], ct[N][N];


int main (){
int n, m, i, j;
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%s", a+1); n = strlen(a+1);
    scanf("%s", b+1); m = strlen(b+1);

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (a[i] == b[j])
                sol[i][j] = sol[i-1][j-1] + 1, ct[i][j] = ct[i][j]+1;
            else
                if (sol[i][j-1] > sol[i-1][j])
                    sol[i][j] = sol[i][j-1], ct[i][j] = ct[i][j-1];
                else
                    if (sol[i-1][j] > sol[i][j-1])
                        sol[i][j] = sol[i-1][j], ct[i][j] = ct[i-1][j];
                    else
                        sol[i][j] = sol[i-1][j], ct[i][j] = (ct[i-1][j] + ct[i][j-1])%666013;
    printf("%d\n", ct[n][m] );

    return 0;
}