#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

const int MOD = 666013;
const int SIGMA = 26;

int main() {
  freopen("subsir.in", "r", stdin);
  freopen("subsir.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);

  string s, t;
  getline(cin, s);
  getline(cin, t);
  int n = s.length();
  int m = t.length();
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  vector<vector<int>> cnt(n + 1, vector<int>(m + 1));
  s = " " + s;
  t = " " + t;
  vector<vector<int>> last(2, vector<int>(SIGMA, -1));
  int lcs = 0;
  for (int i = 1; i <= n; ++i) {
    fill(last[1].begin(), last[1].end(), -1);
    for (int j = 1; j <= m; ++j) {
      if (s[i] != t[j]) {
        last[1][t[j] - 'a'] = j;
        continue;
      }
      dp[i][j] = 1;
      cnt[i][j] = 1;
      for (int c = 0; c < SIGMA; ++c) {
        if (last[0][c] == -1 || last[1][c] == -1) continue;
        int curr_dp = dp[last[0][c]][last[1][c]] + 1;
        int curr_cnt = cnt[last[0][c]][last[1][c]];
        if (curr_dp > dp[i][j]) dp[i][j] = curr_dp, cnt[i][j] = 0;
        if (curr_dp == dp[i][j]) cnt[i][j] += curr_cnt;
        if (cnt[i][j] >= MOD) cnt[i][j] -= MOD;
      }
      lcs = max(lcs, dp[i][j]);
      last[1][t[j] - 'a'] = j;
    }
    last[0][s[i] - 'a'] = i;
  }
  int ans = 0;
  for (int c = 0; c < SIGMA; ++c) {
    if (last[0][c] == -1 || last[1][c] == -1) continue;
    if (dp[last[0][c]][last[1][c]] == lcs) {
      ans += cnt[last[0][c]][last[1][c]];
    }
  }
  cout << ans << endl;

#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}