#include #include #include using namespace atcoder; using namespace std; using namespace boost::multiprecision; #define fst first #define snd second #define fin(...) exit(pt(__VA_ARGS__)) #define pb(...) pop_back(__VA_ARGS__) #define eb(...) emplace_back(__VA_ARGS__) #define ef(...) emplace_front(__VA_ARGS__) #define elif(...) else if(__VA_ARGS__) #define wh(...) while(__VA_ARGS__) #define overload3(a,b,c,d,...) d #define overload4(a,b,c,d,e,...) e #define overload5(a,b,c,d,e,f,...) f #define all1(v) begin(v),end(v) #define all2(v,b) begin(v),begin(v)+b #define all3(v,a,b) begin(v)+a,begin(v)+b #define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__) #define rll1(v) rbegin(v),rend(v) #define rll2(v,b) rbegin(v),rbegin(v)+b #define rll3(v,a,b) rbegin(v)+a,rbegin(v)+b #define rll(...) overload3(__VA_ARGS__,rll3,rll2,rll1)(__VA_ARGS__) #define rep1(b) for(ll _i=0;_i<(ll)(b);_i++) #define rep2(i,b) for(ll i=0;i<(ll)(b);i++) #define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c)) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define per1(a) rep(a) #define per2(i,a) for(ll i=(ll)(a)-1;i>=0;i--) #define per3(i,a,b) for(ll i=(ll)(a)-1;i>=(ll)(b);i--) #define per4(i,a,b,c) for(ll i=(ll)(a)-1;i>=(ll)(b);i-=(ll)(c)) #define per(...) overload4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__) #define fore1(a) rep(sz(a)) #define fore2(a,v) for(auto&&a:v) #define fore3(a,b,v) for(auto&&[a,b]:v) #define fore4(a,b,c,v) for(auto&&[a,b,c]:v) #define fore5(a,b,c,d,v) for(auto&&[a,b,c,d]:v) #define fore(...) overload5(__VA_ARGS__,fore5,fore4,fore3,fore2,fore1)(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;lin(__VA_ARGS__) #define ST(...) string __VA_ARGS__;lin(__VA_ARGS__) using ll=long long; using ld=long double; using v1=vector; using v2=vector; using v3=vector; using v4=vector; using pll=pair; using qll=queue; using sll=set; using msll=multiset; using mll=map; using mint=modint1000000007; ll inf=3e18; ld pi=acosl(-1); ld eps=1e-10; templatell sgn(const T&a){return(a>eps)-(a<-eps);} templatell sgn(const T&a,const T&b){return sgn(a-b);} templatell sz(const T&a){return size(a);} templatevector&operator++(vector&v){for(T&x:v)x++;return v;} templatevector&operator--(vector&v){for(T&x:v)x--;return v;} templatevectoroperator++(vector&v,int){vectorr=v;++v;return r;} templatevectoroperator--(vector&v,int){vectorr=v;--v;return r;} templatevector&operator+=(vector&v,const vectoru){copy(all(u),back_inserter(v));return v;} templatebool operator==(const vector&v,const vector&u){if(sz(v)!=sz(u))return 0;rep(i,sz(v))if(v[i]!=u[i])return 0;return 1;} templatebool operator!=(const vector&v,const vector&u){return!(v==u);} templateusing max_priority_queue=std::priority_queue; templateusing min_priority_queue=std::priority_queue,greater>; templatebool chmax(T&a,const U&b){return abool chmin(T&a,const U&b){return a>b?a=b,1:0;} templateT max(const vector&a){return *max_element(all(a));} templateT min(const vector&a){return *min_element(all(a));} templateconstexpr auto max(T...a){return max(initializer_list>{a...});} templateconstexpr auto min(T...a){return min(initializer_list>{a...});} templateT gcd(const T&a,const A&...b){return gcd(a,gcd(b...));} templateT sum(const vector&a){return accumulate(all(a),T(0));} templateT popcnt(T a){return __builtin_popcountll(a);} templatell lbp(const vector&a,const T&b){return lower_bound(all(a),b)-begin(a);} templatell ubp(const vector&a,const T&b){return upper_bound(all(a),b)-begin(a);} templatepairmima(const T&a,const T&b){return{min(a,b),max(a,b)};} templatepairmima(const pair&p){auto[a,b]=p;return mima(a,b);} templateT at(const vector&v,const ll&i){ll n=sz(v);return v[(i%n+n)%n];} templatevoid sort(vector&v){sort(all(v));} templatevoid sort(vector&v,const F&f){sort(all(v),f);} templatevoid rev(vector&v){reverse(all(v));} templatevoid uni(vector&v){sort(all(v));v.erase(unique(all(v)),end(v));} void sort(string&s){sort(all(s));} void rev(string&s){reverse(all(s));} v1 iota(ll n,ll s=0){v1 a(n);iota(all(a),s);return a;} void emplace_front(v1&v,ll x=0){v.emplace(begin(v),x);} struct fast_ios{fast_ios(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<>(istream&is,mint&x){ll t;is>>t;x=t;return is;} ostream&operator<<(ostream&os,const mint&x){return os<istream&operator>>(istream&is,pair&p){return is>>p.fst>>p.snd;} templateostream&operator<<(ostream&os,const pair&p){return os<istream&operator>>(istream&is,vector&v){fore(x,v)is>>x;return is;} templateostream&operator<<(ostream&os,const vector&v){rep(i,sz(v))os<ostream&operator<<(ostream&os,const vector>&v){rep(i,sz(v))os<ostream&operator<<(ostream&os,const set&s){fore(x,s)os<ostream&operator<<(ostream&os,const map&m){fore(k,v,m)os<fst)?"":"\n");return os;} templateostream&operator<<(ostream&os,const queue&q){auto c=q;wh(sz(c))os<ostream&operator<<(ostream&os,const deque&q){auto c=q;wh(sz(c))os<ostream&operator<<(ostream&os,const max_priority_queue&q){auto c=q;wh(sz(c))os<ostream&operator<<(ostream&os,const min_priority_queue&q){auto c=q;wh(sz(c))os<ll pt(const T&a,const A&...b){cout<ll db(const T&a,const A&...b){cerr<void lin(T&...a){(cin>>...>>a);} templatevoid vin(const ll&i,vector&...a){(cin>>...>>a[i]);} templatevoid vin(vector&a,A&...b){rep(i,sz(a))vin(i,a,b...);} string first(bool f=1){return f?"first":"second";} string First(bool f=1){return f?"First":"Second";} string yes(bool f=1){return f?"yes":"no";} string Yes(bool f=1){return f?"Yes":"No";} string YES(bool f=1){return f?"YES":"NO";} string no(){return "no";} string No(){return "No";} string NO(){return "NO";} string possible(bool f=1){return f?"possible":"impossible";} string Possible(bool f=1){return f?"Possible":"Impossible";} string POSSIBLE(bool f=1){return f?"POSSIBLE":"IMPOSSIBLE";} templatevoid resize(vector&v,const T&a){v.resize(a);} templatevoid resize(vector&vv,const T&a,const A&...b){resize(vv,a);fore(v,vv)resize(v,b...);} templatevoid fill(V&v,const T&x){v=x;} templatevoid fill(vector&vv,const T&x){fore(v,vv)fill(v,x);} void zi(const v1&v,v1&h){fore(x,h)x=lbp(v,x);} templatevoid zi(const v1&v,v1&h,T&...t){zi(v,h);zi(v,t...);} templatev1 zip(T&...a){v1 v;fore(e,{a...})v+=e;uni(v);zi(v,a...);return v;} templatevoid vs(const v1&o,vector&a){vectorc=a;rep(i,sz(a))a[i]=c[o[i]];} templatevoid vs(const v1&o,vector&a,A&...b){vs(o,a);vs(o,b...);} templatepairvsort(const F&f,T&...a){ll n=0;fore(e,{a...})n=sz(e);v1 o=iota(n),p(n);sort(o,f);rep(i,n)p[o[i]]=i;vs(o,a...);return{o,p};} templateT binsearch(const function&j,T o,T n){T D=(*typeid(o).name()=='x'?1:eps);wh(abs(o-n)>D){T m=(o+n)/2;(j(m)?o:n)=m;}return o;} v1 divisor(ll n){mll m;for(ll i=1;i*i<=n;i++){if(n%i==0){m[i]++;m[n/i]++;}}v1 v;fore(x,_,m)v.eb(x);return v;} mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++){wh(n%i==0){m[i]++;n/=i;}}if(n>1)m[n]++;return m;} ll mpow(ll x,ll n,ll m=0){ll r=1;wh(n>0){if(n&1){r*=x;if(m)r%=m;}x*=x;if(m)x%=m;n>>=1;}return r;} ll minv(ll a,ll m){ll b=m,u=1,v=0;wh(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}u%=m;if(u<0)u+=m;return u;} ll lsqrt(ll x){ll r=sqrtl(x)-1;wh(r+1<=x/(r+1))r++;return r;} ll llog2(ll n){ll r=0;wh(n){n>>=1;r++;}return r;} mint mhash(mint a){return a*(a+1346)*(a+9185);} ll bit(ll n){return 1LL<; int main(){ LL(N,K); v1 a(N);lin(a); ST(s); ll M=sz(zip(a)); vector>dp;resize(dp,K+1,N); rep(j,N)dp[0][j]=1; rep(i,1,K+1){ fenwick_treefw(M); rep(j,N){ fw.add(a[j],dp[i-1][j]); dp[i][j]=(s[i-1]=='<'?fw.sum(0,a[j]):fw.sum(a[j]+1,M)); } } pt(sum(dp[K])); }