#AT20. Permutation

Permutation

Original Problem Statement (English)

Source: AtCoder Educational DP Contest - Problem T

Problem Statement

Let NN be a positive integer. You are given a string ss of length N−1N - 1, consisting of < and >.

Find the number of permutations (p1,p2,…,pN)(p_1, p_2, \ldots, p_N) of (1,2,…,N)(1, 2, \ldots, N) that satisfy the following condition, modulo 109+710^9 + 7:

  • For each ii (1≤i≤N−11 \leq i \leq N - 1), pi<pi+1p_i < p_{i + 1} if the ii-th character in ss is <, and pi>pi+1p_i > p_{i + 1} if the ii-th character in ss is >.

Constraints

  • NN is an integer.
  • 2≤N≤30002 \leq N \leq 3000
  • ss is a string of length N−1N - 1.
  • ss consists of < and >.

Input

Input is given from Standard Input in the following format:

N
s

Output

Print the number of permutations that satisfy the condition, modulo 109+710^9 + 7.

Sample Input 1

4
<><

Sample Output 1

5

There are five permutations that satisfy the condition, as follows:

  • (1,3,2,4)(1, 3, 2, 4)
  • (1,4,2,3)(1, 4, 2, 3)
  • (2,3,1,4)(2, 3, 1, 4)
  • (2,4,1,3)(2, 4, 1, 3)
  • (3,4,1,2)(3, 4, 1, 2)

Sample Input 2

5
<<<<

Sample Output 2

1

There is one permutation that satisfies the condition, as follows:

  • (1,2,3,4,5)(1, 2, 3, 4, 5)

Sample Input 3

20
>>>><>>><>><>>><<>>

Sample Output 3

217136290

Be sure to print the number modulo 109+710^9 + 7.