#include<stdio.h>
#include<string.h>

FILE *f=fopen("subsir.in","r"),*g=fopen("subsir.out","w");
int c[501][501];
char x[501],y[501];
unsigned long nr=0;
int main()
{
int i,j;
c[0][0]=0;
fscanf(f,"%s",&x);
fscanf(f,"%s",&y);
for(i=0;i<strlen(x);i++)
        for(j=0;j<strlen(y);j++)
                {
                if(x[i]==y[j])
                        c[i][j]=c[i-1][j-1]+1;
                        else
                        {
                        if(c[i-1][j]>c[i][j-1])
                                c[i][j]=c[i-1][j];
                                else
                                c[i][j]=c[i][j-1];
                        }
                }
for(i=0;i<strlen(x);i++)
        for(j=0;j<strlen(y);j++)
                if(c[strlen(x)-1][strlen(y)-1]==c[i][j] && c[i-1][j] !=c[strlen(x)-1][strlen(y)-1] && c[i][j-1]!=c[strlen(x)-1][strlen(y)-1])
                        nr++;
fprintf(g,"%ld ",nr%666013);
fclose(f);
fclose(g);
return 0;
}