Sour Face

Time limit1sMemory limit1024 MB

Summary

Count the coin-flip sequences that trim characters from both ends until the remaining string is k '>' characters followed by k '<' characters, modulo 10^9 + 7.

Level: Medium5 of 10
Topics: String, Combinatorics, Brute force
Solved: No attempts yet

Problem

Suminee sees the shape >< as a sour face. Specifically, a string that Suminee feels is a sour face is as follows.

> appears $k$ times and < appears $k$ times in a row. Here $k$ is a positive integer of at least $1$ .

By this definition, >><< and >>><<< are both sour faces. However, ><<< is not, because the counts of > and < differ, and <> is not, because the bracket order is wrong.

Suminee wants to remove every character except those that form a sour face from a given string consisting only of > and <. Removing characters one by one is dull, so Seungjun proposed a game in which Suminee makes a sour face.

Flip a coin. If it lands heads, remove the first character of the string. If it lands tails, remove the last character.

Suminee may end the coin flipping at any time. If the string is a sour face when Suminee stops, Suminee wins.

Given a string of length $N$ consisting only of > and <, find the number of ways Suminee can win the game, modulo $1\ 000\ 000\ 007 (10^9 + 7)$ .

Input

The first line contains the size $N$ of the string ( $1 \leq N \leq 2\,000$ ).

The second line contains the string $S$ of length $N$ consisting only of > and <.

Output

Print the number of coin-flip sequences that win the game, modulo $1\ 000\ 000\ 007 (10^9 + 7)$ .

Examples3

Example 1
Input
```
3
><>
```
Expected output
```
1
```
Example 2
Input
```
6
>>><<>
```
Expected output
```
8
```
Example 3
Input
```
2
><
```
Expected output
```
1
```