//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef DEBUG #include "./CompetitiveProgrammingCpp/debug.hpp" #include "./CompetitiveProgrammingCpp/Timer.hpp" #include "./CompetitiveProgrammingCpp/sample.hpp" #else #define dump(...) templateconstexpr inline auto d_val(T a, T b) { return a; } #endif /* macro */ #define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i) #define RFOR(i, b, e) for(ll i = (ll)((e)-1); i >= (ll)(b); --i) #define REP(i, n) FOR(i, 0, (n)) #define RREP(i, n) RFOR(i, 0, (n)) #define REPC(x,c) for(const auto& x:(c)) #define REPI2(it,b,e) for(auto it = (b); it != (e); ++it) #define REPI(it,c) REPI2(it, (c).begin(), (c).end()) #define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend()) #define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);) #define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end()) #define ALL(x) (x).begin(),(x).end() #define cauto const auto& /* macro func */ template inline auto sort(T& t) { std::sort(ALL(t)); } template inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); } template inline auto unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); } template inline auto chmax(T& t, const S& s) { if(s > t) { t = s; return true; } return false; } template inline auto chmin(T& t, const S& s) { if(s < t) { t = s; return true; } return false; } inline auto BR() { std::cout << "\n"; } /* type define */ using ll = long long; using VS = std::vector; using VL = std::vector; using VVL = std::vector; using VVVL = std::vector; using VVVVL = std::vector; using VVVVVL = std::vector; using VD = std::vector; template using V = std::vector; template using P = std::pair; using PAIR = P; /* using std */ using std::cout; constexpr char endl = '\n'; using std::cin; using std::pair; using std::string; using std::stack; using std::queue; using std::deque; using std::vector; using std::list; using std::map; using std::unordered_map; using std::multimap; using std::unordered_multimap; using std::set; using std::unordered_set; using std::unordered_multiset; using std::multiset; using std::bitset; using std::priority_queue; /* Initial processing */ struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing; /* Remove the source of the bug */ auto pow(signed, signed) { assert(false); } /* define hash */ namespace std { template <> class hash> { public: size_t operator()(const std::pair& x) const { return hash()(1000000000 * x.first + x.second); } }; } /* input */ template std::istream& operator >> (std::istream& is, vector& vec) { for(T& x : vec) is >> x; return is; } /* constant value */ constexpr ll MOD = 1000000007; // constexpr ll MOD = 998244353; //============================================================================================= template class isMonoid { template static auto check(U x) -> decltype(x.binaryOperation(x), std::true_type{}); static std::false_type check(...); public: static bool const value = decltype(check(std::declval()))::value; }; template::value, std::nullptr_t> = nullptr > class SegmentTree { private: const int m_size; vector m_node; int calcSize(int n) const { int size = 1; while(size < n) { size <<= 1; }return size; } auto _query(int a, int b) const { return _query(a, b + 1, 0, 0, m_size); } auto _query(int a, int b, int k, int l, int r)const { if(r <= a || b <= l) { return Monoid(); } if(a <= l && r <= b) { return m_node[k]; } return _query(a, b, 2 * k + 1, l, (l + r) / 2).binaryOperation( _query(a, b, 2 * k + 2, (l + r) / 2, r) ); } public: SegmentTree(int n) : m_size(calcSize(n)), m_node(m_size * 2 - 1) {} auto add(int itr, Monoid&& val) { int i = itr + m_size - 1; m_node[i] = std::forward(val); while(i > 0) { i = (i - 1) / 2; m_node[i] = m_node[i * 2 + 1].binaryOperation(m_node[i * 2 + 2]); } } auto query(int a, int b, int k, int l, int r)const { return _query(a, b, k, l, r).m_val; } auto query(int a, int b)const { return query(a, b + 1, 0, 0, m_size); } }; template< class S, // 要素の型 S element, // 元 class T // lambdaはC++20じゃないと渡せなかった... // S T(S, S) // 2項演算子 > struct Monoid { S m_val; Monoid() :m_val(element) {} Monoid(S val) :m_val(val) {} Monoid binaryOperation(const Monoid& m2)const { return T()(m_val, m2.m_val); } }; signed main() { ll n, k; cin >> n >> k; VL a(n); string s; cin >> a >> s; struct Functor { auto operator()(ll a, ll b)const { return (a + b) % MOD; } }; using M = Monoid; auto tree = SegmentTree(n); auto itox = a; sort(itox); unique(itox); ll sz = itox.size(); map xtoi; REP(i, sz) { xtoi.emplace(itox[i], i); } V> dp(k + 1, SegmentTree(sz)); REP(i, n) { FOR(j, 1, k + 1) { if(s[j - 1] == '<') { ll x = a[i]; ll it = xtoi[x]; ll ad = dp[j - 1].query(0, it - 1); ll now = dp[j].query(it, it); dp[j].add(it, now + ad); } else { ll x = a[i]; ll it = xtoi[x]; ll ad = dp[j - 1].query(it + 1, sz - 1); ll now = dp[j].query(it, it); dp[j].add(it, now + ad); } } ll x = a[i]; auto it = xtoi[x]; ll now = dp[0].query(it, it); dp[0].add(it, now + 1); } ll ans = dp[k].query(0, sz - 1); cout << ans << endl; }