#include<stdio.h>
#include<string.h>
int maxim ( int x , int y ){
    if(x<y)
        return y;
    return x;
}
char s1[504],s2[504];
int a[505][505],nr[505][505];
int main(){
    int n1,n2,i,j;
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%s",&s1);
    scanf("%s",&s2);
    n1=strlen(s1);
    n2=strlen(s2);
    strcpy(s1+1,s1);
    strcpy(s2+1,s2);
    for(i=1;i<=n1;i++)
        for(j=1;j<=n2;j++)
            if(s1[i]==s2[j])
                a[i][j]=1+a[i-1][j-1];
            else
                a[i][j]=maxim(a[i-1][j],a[i][j-1]);
    for(i=1;i<=n1;i++)
        for(j=1;j<=n2;j++)
            if(i==1||j==1)
                nr[i][j]=1;
            else
                if(s1[i]==s2[j])
                    nr[i][j]=nr[i-1][j-1];
                else{
                    if(a[i-1][j]==a[i][j])
                        nr[i][j]=(nr[i][j]+nr[i-1][j])%666013;
                    if(a[i][j-1]==a[i][j])
                        nr[i][j]=(nr[i][j]+nr[i][j-1])%666013;
                    if(a[i][j]==a[i-1][j-1])
                        nr[i][j]=(nr[i][j]-nr[i-1][j-1]+666013)%666013;
                }
    printf("%d\n",nr[n1][n2]);
    return 0;
}