Old C is a programmer. As an excellent programmer, Old C owns a unique keyboard, which is said to significantly increase the speed of writing programs and allows the written programs to run extremely fast under some mysterious power.

Little Q is also a programmer. One day, he sneaked into Old C's house, wanting to see what was so special about this keyboard. He discovered that the keyboard has $n$ keys, and although these $n$ keys are arranged in a neat row, the heights of each key are distinct. The clever Little Q immediately represented the height of each key as an integer from $1$ to $n$, resulting in a permutation $h_1, h_2, \dots, h_n$ of $1 \dots n$. To avoid having his keyboard exactly the same as Old C's, Little Q decided to record the height relationships of several keys. As a programmer, Little Q certainly wouldn't just pick a few at random; instead, he chose a very regular set of keys: for $i = 2, 3, \dots, n$, Little Q recorded a character < or >, indicating $h_{\lfloor i/2 \rfloor} < h_i$ or $h_{\lfloor i/2 \rfloor} > h_i$ respectively. Thus, Little Q obtained a string of length $n-1$, and went home happily.

Now, Little Q wants to know how many keyboards satisfy the height relationships he recorded. Although Little Q does not want his keyboard to be exactly the same as Old C's, he will count all keyboards that satisfy the requirements. The answer might be very large, so you only need to tell Little Q the result modulo $1,000,000,007$.

Input

The input contains one line, which includes an integer $n$ and a string of length $n-1$ consisting only of < and >, separated by a space, representing the information recorded by Little Q.

Output

Output one integer, representing the result modulo $1,000,000,007$.

Examples

Input 1

5 <>><

Output 1

3

Note 1

There are 5 keys. The 1st key is compared to the 2nd, the 1st to the 3rd, the 2nd to the 4th, and the 2nd to the 5th. The possible height permutations for these 5 keys are $(2, 4, 1, 3, 5)$, $(3, 4, 1, 2, 5)$, $(3, 4, 2, 1, 5)$.

Input 2

5 <<<<

Output 2

8

Input 3

5 <<>>

Output 3

18

Subtasks