#include <stdio.h>

typedef struct{
    int x,y;
}coor;

char s1[505],s2[505];
int DP[505][505],c_size[505],N,M,nr;
coor c[505][505];

void rec(int p, int x, int y){
    for(int i=0;i<c_size[p];++i){
        if(c[p][i].x>x && c[p][i].y>y){
            if(p==DP[N][M]){
                nr++;
                nr%=666013;
            }
            else rec(p+1,c[p][i].x,c[p][i].y);
        }
    }
}

static inline int MAX(int a, int b){
    return (a>=b ? a : b);
}

int main(void){
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);

    scanf("%s %s",&s1,&s2);
    N=strlen(s1);
    M=strlen(s2);

    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j){
            DP[i][j]=MAX(DP[i-1][j],DP[i][j-1]);
            if(s1[i-1]==s2[j-1]){
                DP[i][j]=MAX(DP[i][j],DP[i-1][j-1]+1);
                if(DP[i-1][j]==DP[i][j-1] && DP[i-1][j]==DP[i][j]-1){
                    c[DP[i][j]][c_size[DP[i][j]]].x=i;
                    c[DP[i][j]][c_size[DP[i][j]]++].y=j;
                }
            }
        }
    rec(1,0,0);
    printf("%d",nr);

    return 0;
}