#include <stdio.h>
#define MAXL 500
#define SIGMA 26
#define MOD 666013
char s1[MAXL + 2], s2[MAXL + 2], fin[SIGMA];
int f1[MAXL][SIGMA], f2[MAXL][SIGMA], d[MAXL][MAXL], n[MAXL][MAXL];

inline int max2(int a, int b){
  return a > b ? a : b;
}

inline int len(char *s){
  int i = 0;
  while(s[i] != '\n')
    i++;
  return i;
}

inline void calcf(char *s, int f[MAXL][SIGMA], int l){
  int i, j;
  for(j = 0; j < SIGMA; j++)
    f[0][j] = -1;
  for(i = 1; i < l; i++){
    for(j = 0; j < SIGMA; j++){
      if(s[i - 1] == j + 'a')
        f[i][j] = i - 1;
      else
        f[i][j] = f[i - 1][j];
    }
  }
}

int main(){
  FILE *in = fopen("subsir.in", "r");
  int l1, l2;
  fgets(s1, MAXL + 2, in);
  l1 = len(s1);
  fgets(s2, MAXL + 2, in);
  l2 = len(s2);
  fclose(in);
  calcf(s1, f1, l1);
  calcf(s2, f2, l2);
  int i, j, k, rez = 0;
  for(i = 0; i < l1; i++){
    for(j = 0; j < l2; j++){
      if(s1[i] == s2[j]){
        d[i][j] = 1;
        for(k = 0; k < SIGMA; k++)
          if(f1[i][k] != -1 && f2[j][k] != -1)
            d[i][j] = max2(d[i][j], d[f1[i][k]][f2[j][k]] + 1);
        if(d[i][j] == 1)
          n[i][j] = 1;
        for(k = 0; k < SIGMA; k++){
          if(f1[i][k] != -1 && f2[j][k] != -1 && d[f1[i][k]][f2[j][k]] >= d[i][j] - 1){
            n[i][j] += n[f1[i][k]][f2[j][k]];
            if(n[i][j] >= MOD)
              n[i][j] -= MOD;
          }
        }
      }
      rez = max2(rez, d[i][j]);
    }
  }
  int nr = 0;
  for(i = l1 - 1; i >= 0; i--){
    for(j = l2 - 1; j >= 0; j--){
      if(s1[i] == s2[j] && !fin[s1[i] - 'a'] && d[i][j] == rez){
        nr += n[i][j];
        if(nr >= MOD)
          nr -= MOD;
        fin[s1[i] - 'a'] = 1;
      }
    }
  }
  FILE *out = fopen("subsir.out", "w");
  fprintf(out, "%d", nr);
  fclose(out);
  return 0;
}