#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];
  }
}

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

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 = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        cnt[i][j] = cnt[i - 1][j - 1] + (dp[i][j] == 1);
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        bool i1 = (dp[i][j] == dp[i - 1][j]);
        bool i2 = (dp[i][j] == dp[i][j - 1]);
        cnt[i][j] = (cnt[i - 1][j] * i1 + cnt[i][j - 1] * i2 - (i1 && i2 && dp[i - 1][j - 1] == dp[i][j]) * cnt[i - 1][j - 1]);
        cnt[i][j] %= mod;
        if (cnt[i][j] < 0) {
          cnt[i][j] += mod;
        }
      }
    }
  }

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

  return 0;
}