Problem Statement

You are given a sequence of positive integers $A = ( A_{1}, A_{2}, \dots, A_{N} )$ of length $N$ and a string $s$ of length $K$ consisting only of < and >.
Below, the $i$-th $(1 \leq i \leq K)$ character from the beginning of $s$ is denoted by $s_{i}$.

Find the number of ways to choose a tuple of integers $(x_{1}, x_{2}, \dots, x_{K+1})$ satisfying $1 \leq x_{1} < x_{2} < \cdots < x_{K+1} \leq N$ such that,
for all $i = 1, 2, \dots, K$, both of the following $2$ conditions hold.

• If $s_{i}$ is <, then $A_{x_{i} } < A_{x_{i+1} }$.

• If $s_{i}$ is >, then $A_{x_{i} } > A_{x_{i+1} }$.

Since the answer can be very large, print the remainder when it is divided by $10^{9}+7$.

Constraints

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

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

• $N$, $K$, and $A_{i}$ $(1 \leq i \leq N)$ are all integers.

• $s$ is a string of length $K$ consisting only of < and >.

Input

The input is given in the following format.

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

• Line $1$ contains $N$, $K$ in this order, separated by half-width spaces.

• Line $2$ contains $A_{1}, A_{2}, \dots, A_{N}$ in this order, separated by half-width spaces.

• Line $3$ contains $s$.

Output

Print the answer on $1$ line, followed by a newline.

Sample

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