T - Permutation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

問題文

N を正整数とします。 長さ N - 1 の文字列 s が与えられます。 s<> からなります。

(1, 2, \ldots, N) を並べ替えた順列 (p_1, p_2, \ldots, p_N) であって、次の条件を満たすものは何通りでしょうか? 10^9 + 7 で割った余りを求めてください。

  • i (1 \leq i \leq N - 1) について、si 文字目が < の場合は p_i < p_{i + 1} であり、si 文字目が > の場合は p_i > p_{i + 1} である。

制約

  • N は整数である。
  • 2 \leq N \leq 3000
  • s は長さ N - 1 の文字列である。
  • s<> からなる。

入力

入力は以下の形式で標準入力から与えられる。

N
s

出力

条件を満たす順列は何通りか? 10^9 + 7 で割った余りを出力せよ。


入力例 1

4
<><

出力例 1

5

条件を満たす順列は次の 5 通りです。

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

入力例 2

5
<<<<

出力例 2

1

条件を満たす順列は次の 1 通りです。

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

入力例 3

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

出力例 3

217136290

答えを 10^9 + 7 で割った余りを出力することを忘れずに。

Score : 100 points

Problem Statement

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

Find the number of permutations (p_1, p_2, \ldots, p_N) of (1, 2, \ldots, N) that satisfy the following condition, modulo 10^9 + 7:

  • For each i (1 \leq i \leq N - 1), p_i < p_{i + 1} if the i-th character in s is <, and p_i > p_{i + 1} if the i-th character in s is >.

Constraints

  • N is an integer.
  • 2 \leq N \leq 3000
  • s is a string of length N - 1.
  • s 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 10^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, 4, 2, 3)
  • (2, 3, 1, 4)
  • (2, 4, 1, 3)
  • (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)

Sample Input 3

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

Sample Output 3

217136290

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