#include <algorithm>
#include <cstdio>
#include <fstream>
#include <iostream>

class LCSTable
{
  private:
    size_t m_;
    size_t n_;
    size_t mod_;
    size_t* data_;
    size_t* sol_;

    size_t getSolAt(size_t i, size_t j) const
    {
      return sol_[i + j * (m_ + 1)];
    }

    void setSolAt(size_t i, size_t j, size_t val)
    {
      sol_[i + j * (m_ + 1)] = val;
    }

  public:
    LCSTable(size_t m, size_t n, size_t mod)
    : m_(m), n_(n), mod_(mod)
    {
      data_ = new size_t [(m + 1) * (n + 1)];
      sol_ = new size_t [(m + 1) * (n + 1)];
    }

    LCSTable(const LCSTable& other)
    : m_(other.m_),
      n_(other.n_),
      mod_(other.mod_),
      data_(new size_t [(other.m_ + 1) * (other.n_ + 1)]),
      sol_(new size_t [(other.m_ + 1) * (other.n_ + 1)])
    {
      std::copy(other.data_,
                other.data_ + (other.m_ + 1) * (other.n_ + 1),
                data_);
    }

    ~LCSTable()
    {
      delete [] data_;
      delete [] sol_;
    }

    LCSTable& operator=(const LCSTable& rhs) {
      if (this != &rhs) {
        m_ = rhs.m_;
        n_ = rhs.n_;
        mod_ = rhs.mod_;
        size_t size = (rhs.m_ + 1) * (rhs.n_ + 1);
        delete [] data_;
        data_ = new size_t [size];
        std::copy(rhs.data_,
                  rhs.data_ + size,
                  data_);
        delete [] sol_;
        sol_ = new size_t [size];
        std::copy(rhs.sol_,
                  rhs.sol_ + size,
                  sol_);
      }
      return *this;
    }

    size_t getAt(size_t i, size_t j) const
    {
      return data_[i + j * (m_ + 1)];
    }

    void setAt(size_t i, size_t j, size_t value)
    {
      data_[i + j * (m_ + 1)] = value;
    }

    template <class T>
    size_t build(const T& X, const T& Y)
    {
      for (size_t i = 0; i <= m_; ++i) {
        setAt(i, 0, 0);
        setSolAt(i, 0, 1);
      }

      for (size_t j = 0; j <= n_; ++j) {
        setAt(0, j, 0);
        setSolAt(0, j, 1);
      }

      for (size_t i = 0; i < m_; ++i) {
        for (size_t j = 0; j < n_; ++j) {
          if (X[i] == Y[j]) {
            setAt(i + 1, j + 1, getAt(i, j) + 1);
          } else {
            setAt(i + 1, j + 1, std::max(getAt(i + 1, j), getAt(i, j + 1)));
          }
        }
      }

      for (size_t i = 1; i <= m_; i++) {
        for (size_t j = 1; j <= n_; j++) {
          int dij = 0;
          if (X[i - 1] == Y[j - 1]) {
            dij = getSolAt(i - 1, j - 1);
          } else if (getAt(i, j) == getAt(i - 1, j)) {
            dij = (dij + getSolAt(i - 1, j)) % mod_;
          }

          if (getAt(i, j) == getAt(i, j - 1)) {
            dij = (dij + getSolAt(i, j - 1)) % mod_;
          }

          if (getAt(i, j) == getAt(i - 1, j - 1)) {
            dij = (dij - getSolAt(i - 1, j - 1) + mod_) % mod_;
          }

          setSolAt(i, j, dij);
        }
      }

      return getSolAt(m_, n_);
    }
};

int main(int argc, char** argv)
{

  std::ifstream in("subsir.in");
  std::ofstream out("subsir.out");
  std::string s1;
  std::string s2;
  in >> s1;
  in >> s2;
  int m = s1.size();
  int n = s2.size();
  int max = std::max(m, n);
  int min = std::min(m, n);

  LCSTable lcs(max, min, 666013);

  if (m == max) {
    out << lcs.build<std::string>(s1, s2);
  } else {
    out << lcs.build<std::string>(s2, s1);
  }

  in.close();
  out.close();
  return 0;
}