/* -*- coding: utf-8 -*- * * 1996.cc: No.1996 <>< - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_N = 1500; const int MOD = 1000000007; /* typedef */ template struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) {} MI(long long _v): v(_v % MOD) {} MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } }; typedef MI mi; template struct BIT { int n; vector bits; BIT() {} BIT(int _n) { init(_n); } void init(int _n) { n = _n; bits.assign(n + 1, 0); } T sum(int x) { x = min(x, n); T s = 0; while (x > 0) { s += bits[x]; x -= (x & -x); } return s; } void add(int x, T v) { if (x <= 0) return; while (x <= n) { bits[x] += v; x += (x & -x); } } int lower_bound(T v) { int k = 1; while ((k << 1) <= n) k <<= 1; int x = 0; for (; k > 0; k >>= 1) if (x + k <= n && bits[x + k] < v) { x += k; v -= bits[x]; } return x + 1; } }; /* global variables */ int as[MAX_N], uas[MAX_N]; char s[MAX_N + 4]; BIT bits[MAX_N]; /* subroutines */ /* main */ int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", as + i); scanf("%s", s); copy(as, as + n, uas); sort(uas, uas + n); int m = unique(uas, uas + n) - uas; for (int i = 0; i <= k; i++) bits[i].init(m); for (int i = 0; i < n; i++) { int ai = lower_bound(uas, uas + m, as[i]) - uas; for (int j = k - 1; j >= 0; j--) { mi dj = (s[j] == '<') ? bits[j].sum(ai) : bits[j].sum(m) - bits[j].sum(ai + 1); if (dj.v != 0) bits[j + 1].add(ai + 1, dj); } bits[0].add(ai + 1, 1); } printf("%d\n", bits[k].sum(m).v); return 0; }