問題文

長さ $N$ の正整数列 $A = ( A_{1}, A_{2}, \dots, A_{N} )$ と、<と>のみからなる長さ $K$ の文字列 $s$ が与えられます。
以下、$s$ の先頭から $i$ $(1 \leq i \leq K)$ 番目の文字を $s_{i}$ と表します。

$1 \leq x_{1} < x_{2} < \cdots < x_{K+1} \leq N$ を満たす整数の組 $(x_{1}, x_{2}, \dots, x_{K+1})$ を選ぶ方法であって、
$i = 1, 2, \dots, K$ すべてに対して次の $2$ つの条件をともに満たすものの個数を求めてください。

• $s_{i}$ が < ならば $A_{x_{i} } < A_{x_{i+1} }$

• $s_{i}$ が > ならば $A_{x_{i} } > A_{x_{i+1} }$

ただし、答えは非常に大きくなる可能性があるので、$10^{9}+7$ で割った余りを出力してください。

制約

• $1 \leq K < N \leq 1500$

• $1 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

• $N$, $K$ 及び $A_{i}$ $(1 \leq i \leq N)$ はすべて整数

• $s$ は<と>のみからなる長さ $K$ の文字列

入力

入力は次の形式で与えられます。

$N$ $K$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
$s$

• $1$ 行目には $N$, $K$ がこの順に半角スペース区切りで与えられる

• $2$ 行目には $A_{1}, A_{2}, \dots, A_{N}$ がこの順に半角スペース区切りで与えられる

• $3$ 行目には $s$ が与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

5 3
2 3 1 1 4
<><

2

6 4
1 1 2 5 1 4
>><<

0

20 5
13359410 197769 10910581 3 512 5732 9026607 22294 3997084 262110309 51421 728930621 353629015 49 1907 208452 13 13760365 6779710 3484117
><><<

1744

40 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
<<<<<<<<<<<<<<<<<<<

846527861