#include <cstdio>
using namespace std;

int main () {
  int const MODULO = 666013;
  int const MAXN = 500;
  char A[MAXN], B[MAXN], ch;
  int lenA, lenB, lcs[1+MAXN][1+MAXN], count[1+MAXN][1+MAXN], i, j;
  FILE * io = fopen("subsir.in", "r");
  bool isLetter;
  do { ch = fgetc(io); } while (('a' > ch || 'z' < ch) && ('A' > ch && 'Z' < ch));
  A[0] = ch; lenA = 1;
  do {
    ch = fgetc(io);
    if((isLetter = (('a' <= ch && 'z' >= ch) || 
                    ('A' <= ch && 'Z' >= ch))   )) {
      A[lenA] = ch;
      ++ lenA;
    }
  } while(isLetter);
  do { ch = fgetc(io); } while (('a' > ch || 'z' < ch) && ('A' > ch && 'Z' < ch));
  B[0] = ch; lenB = 1;
  do {
    ch = fgetc(io);
    if((isLetter = (('a' <= ch && 'z' >= ch) ||
                    ('A' <= ch && 'Z' >= ch)   )   )) {
      B[lenB] = ch;
      ++ lenB;
    }
  } while (isLetter);
  fclose(io);

  for(i=0;i<=lenA;i++) {
    lcs[i][0] = 0;
    count[i][0] = 1 % MODULO;
  }
  for(j=0;j<=lenB;j++) {
    lcs[0][j] = 0;
    count[0][j] = 1 % MODULO;
  }
  for(i=1;i<=lenA;i++) {
    for(j=1;j<=lenB;j++) {
      if(A[i] == B[j]) {
        lcs[i][j] = 1 + lcs[-1+i][-1+j];
        count[i][j] = count[-1+i][-1+j];
      } else {
        if(lcs[i-1][j] > lcs[i][j-1]) {
          lcs[i][j] = lcs[i-1][j];
          count[i][j] = count[i-1][j];
        } else if(lcs[i-1][j] == lcs[i][j-1]) {
          lcs[i][j] = lcs[i-1][j];
          count[i][j] = (count[i-1][j] + count[i][j-1]) % MODULO;
        } else {
          lcs[i][j] = lcs[i][j-1];
          count[i][j] = count[i][j-1];
        }
      }
    }
  }
  io = fopen("subsir.out", "w");
  fprintf(io, "%d\n", count[lenA][lenB]);
  fclose(io);
  return 0;
}