Problem Description

Old C is a programmer.

As an excellent programmer, Old C has a uniquely designed keyboard, which is said to significantly enhance programming speed and make the programs run very fast under the influence of some magical force.

Xiao Q is also a programmer. One day, he sneaked into Old C's home to see what was so special about this keyboard. He found that the keyboard has $n$ keys, which are neatly arranged in a row, but each key has a different height. Smart Xiao Q immediately represented the height of each key with integers from $1$ to $n$, resulting in a permutation of $1$ to $n$: $h_1, h_2, \cdots, h_n$.

To create a new keyboard (where each key's height is also a permutation of $1$ to $n$) without being identical to Old C's keyboard, Xiao Q decided to record the height relationships of several key pairs. As a programmer, Xiao Q did not randomly choose pairs but selected them very systematically: for $i = 2, 3, \cdots, n$, Xiao Q recorded a character < or >, indicating $h_{\frac{i}{2}} < h_i$ or $h_{\frac{i}{2}} > h_i$. Thus, Xiao Q obtained a string of length $n-1$ and happily went home.

Now, Xiao Q wants to know how many keyboards satisfy the height relationships he recorded. Although Xiao Q does not want his keyboard to be exactly the same as Old C's, an identical keyboard is also considered a valid one. The answer may be very large, so you only need to tell Xiao Q the result modulo $1,000,000,007$.

Input Format

The input consists of two parts: a positive integer $n$ and a string of length $n-1$ containing only < and >, representing the number of keys on the keyboard and the information recorded by Xiao Q, respectively. There is a space between the integer and the string.

Output Format

The output consists of one line containing an integer, which is the answer modulo $1,000,000,007$.

Sample Input and Output

Sample Input #1

5 <>><

Sample Output #1

3

Sample Input #2

5 <<<<

Sample Output #2

8

Sample Input #3

5 <<>>

Sample Output #3

18

见题面 Input 部分

见题面 Output 部分