Submission #11926086


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
  public:
    int64_t a;

    explicit constexpr modint(const int64_t x = 0) noexcept :
      a((x % M + M) % M) {}
    constexpr int64_t &value() noexcept { return a; }
    constexpr const int64_t &value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
      return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
      return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
      return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
      return modint(*this) /= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept {
      a += rhs.a;
      if (a >= M) {
        a -= M;
      }
      return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept {
      if (a < rhs.a) {
        a += M;
      }
      a -= rhs.a;
      return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept {
      a = a * rhs.a % M;
      return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept {
      int64_t exp = M - 2;
      while (exp) {
        if (exp % 2) {
          *this *= rhs;
        }
        rhs *= rhs;
        exp /= 2;
      }
      return *this;
    }
    constexpr modint pow(ll t) const {
      if (!t) return modint(1);
      modint a = pow(t>>1);
      a *= a;
      if (t&1) a *= *this;
      return a;
    }
};
// }}}
using mint = modint<1000000007>;

ll N;
string s;
mint dp[5000][5000];
mint psum[5000];

signed main() {
  cin >> N >> s;
  rep(i, N)
    dp[0][i] += mint(1);
  rep(i, N) {
    ll bi = i-1;
    if (bi < 0) continue;
    psum[0] = dp[bi][0];
    for (ll j=1; j<N; j++)
      psum[j] = psum[j-1] + dp[bi][j];
    rep(j, N) {
      if (s[i-1] == '>') dp[i][j] = psum[N-i] - psum[j];
      if (s[i-1] == '<') dp[i][j] = psum[j];
    }
  }
  cout << dp[N-1][0].value() << endl;
  return 0;
}

Submission Info

Submission Time
Task T - Permutation
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2537 Byte
Status
Exec Time 73 ms
Memory 118400 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
× 17
Set Name Test Cases
All 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 384 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 67 ms 118400 KB
1_03 73 ms 118400 KB
1_04 70 ms 118400 KB
1_05 70 ms 118400 KB
1_06 70 ms 118400 KB
1_07 69 ms 116352 KB
1_08 69 ms 116352 KB
1_09 69 ms 116352 KB
1_10 68 ms 116352 KB
1_11 68 ms 116352 KB
1_12 66 ms 114304 KB
1_13 70 ms 118400 KB