#include <iostream>
#include <fstream>
#include <cstring>

#define MODULO 666013

int lmax[550][550];
int ct[550][550];
int prevs1[550]['z' - 'a' + 1], prevs2[550]['z' - 'a' + 1];

void fill_prev(char* s, int n, int prev[]['z' - 'a' + 1]) {
  int prevl['z' - 'a' + 1] = { 0 };

  for (int i = 1; i <= n; ++i) {
    memcpy(prev[i], prevl, sizeof(int) * ('z' - 'a' + 1));
    prevl[s[i] - 'a'] = i;
  }
}

int main() {
  FILE* in = fopen("subsir.in", "r");
  FILE* out = fopen("subsir.out", "w");

  char s1[550], s2[550];
  fscanf(in, "%s%s", s1 + 1, s2 + 1);
  int n1 = strlen(s1 + 1), n2 = strlen(s2 + 1);
  fill_prev(s1, n1, prevs1);
  fill_prev(s2, n2, prevs2);

  for (int i = 1; i <= n1; ++i) {
    for (int j = 1; j <= n2; ++j) {
      if (lmax[i - 1][j] > lmax[i][j - 1]) {
        // Assume you're importing the max from (i - 1, j). Copy over ct.
        lmax[i][j] = lmax[i - 1][j];
        ct[i][j] = ct[i - 1][j];
        // See if you can make s1[i] participate for the same lmax.
        int prevind = prevs2[j][s1[i] - 'a'];
        if (prevind && lmax[i - 1][prevind - 1] + 1 == lmax[i][j]) {
          ct[i][j] += std::max(1, ct[i - 1][prevind - 1]);
          ct[i][j] %= MODULO;
       }
      } else if (lmax[i - 1][j] <= lmax[i][j - 1]) {
        // Assume you're importing the max from (i, j - 1). Copy over ct.
        lmax[i][j] = lmax[i][j - 1];
        ct[i][j] = ct[i][j - 1];
        // See if you can make s2[j] participate for the same lmax.
        int prevind = prevs1[i][s2[j] - 'a'];
        if (prevind && lmax[prevind - 1][j - 1] + 1 == lmax[i][j]) {
          ct[i][j] += std::max(1, ct[prevind - 1][j - 1]);
          ct[i][j] %= MODULO;
        }
      }

      // Otherwise, this is truly a new max.
      if (s1[i] == s2[j] && lmax[i][j] < lmax[i - 1][j - 1] + 1) {
        lmax[i][j] = lmax[i - 1][j - 1] + 1;
        ct[i][j] = std::max(1, ct[i - 1][j - 1]);
      }
    }
  }

  fprintf(out, "%d\n", ct[n1][n2]);

  fclose(in);
  fclose(out);

  return 0;
}