#include <fstream>

using namespace std;

ifstream cin ("subsir.in");
ofstream cout ("subsir.out");

const int MOD = 666013;

int n, m;

string a, b;

int maxLength[505][505], noWays[505][505];

int main() {
  cin >> a >> b;
  n = a.size(), m = b.size();
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      if(a[i - 1] == b[j - 1]) {
        maxLength[i][j] = maxLength[i - 1][j - 1] + 1;
        noWays[i][j] = noWays[i - 1][j - 1];
        if(maxLength[i][j] == 1)
          noWays[i][j] = 1;
      } else {
        maxLength[i][j] = max(maxLength[i - 1][j], maxLength[i][j - 1]);
        if(maxLength[i][j] == maxLength[i - 1][j])
          noWays[i][j] += noWays[i - 1][j];
        if(maxLength[i][j] == maxLength[i][j - 1])
          noWays[i][j] += noWays[i][j - 1];
        if(maxLength[i - 1][j - 1] == maxLength[i][j] && maxLength[i - 1][j] == maxLength[i][j - 1])
          noWays[i][j] -= noWays[i - 1][j - 1];
        if(noWays[i][j] > MOD)
          noWays[i][j] -= MOD;
        if(noWays[i][j] < 0)
          noWays[i][j] += MOD;
      }
    }
  }
  cout << noWays[n][m];
  return 0;
}