#include <iostream>
#include <cstdio>

using namespace std;

void put(string s, int &n, int a[]) {
  n = (int) s.size();
  for (int i = 1; i <= n; i++) {
    a[i] = s[i - 1] - 'a';
  }
}

const int N = 500 + 7;
int n, a[N];
int m, b[N];
int dp[N][N];
int distinct[N][N];

int rep(int num) {
  int mod = 666013;
  num %= mod;
  if (num < 0) {
    return num + mod;
  }
  return num;
}

int main() {
  freopen ("subsir.in", "r", stdin);
  freopen ("subsir.out", "w", stdout);

  string s, t;
  cin >> s >> t;
  put(s, n, a);
  put(t, m, b);

  for (int i = 0; i <= max(n, m); i++) {
    distinct[0][i] = distinct[i][0] = 1;
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
        distinct[i][j] = distinct[i - 1][j - 1];
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        distinct[i][j] = rep(distinct[i - 1][j] + distinct[i][j - 1] - distinct[i - 1][j - 1]);
      }
    }
  }

  cout << distinct[n][m] << '\n';

  return 0;
}