#include <stdio.h>
#include <string>
#define 512 512 
#define 666013 666013 
char a[512],b[512]; 
int n,m,i,j,D[512][512],c[512][512]; 
int main() 
{ 
    freopen ("subsir.in", "r", stdin); 
    freopen ("subsir.out", "w", stdout); 
    scanf("%s", a+1); scanf("%s", b+1); 
    n=strlen(a+1);
    m=strlen(b+1); 
    for (i=0; i<=n; i++) 
        c[i][0] = 1; 
    for (j=0; j<=m; j++)
        c[0][j] = 1; 
    for (i=1; i<=n; i++) 
        for (j=1; j<=m; j++){
            if (a[i] == b[j]){
               D[i][j]=D[i-1][j-1] + 1;
               c[i][j] = c[i-1][j-1];
               }
            else if (D[i-1][j] == D[i][j-1]){
                 D[i][j]=D[i-1][j];
                 c[i][j]=(c[i-1][j]+c[i][j-1])%666013;
                 if (D[i-1][j-1]==D[i-1][j])c[i][j]=(c[i][j]-c[i-1][j-1]+666013)%666013;
                 }
                 else if (D[i-1][j] > D[i][j-1]){
                         D[i][j]=D[i-1][j];
                         c[i][j] = c[i-1][j];}
                         else if (D[i-1][j] < D[i][j-1]){
                              D[i][j] = D[i][j-1];
                              c[i][j] = c[i][j-1];
                              }
                         }
        printf("%d\n",c[n][m]);
    return 0;
}