Permutation

有一个长为 $N$ 的正整数排列。给定一个由 `<` 和 `>` 组成长为 $N-1$ 的的字符串。 对于任意满足 $1 \le i \le N-1$ 的字符 $s_i$，如果 $s_i$ 是 `<` 则 $P_i<P_{i+1}$、如果 $s_i$ 是 `>` 则 $P_i>P_{i+1}$。求满足这样的性质的排列 $P$ 的方案数。

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_t $ 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 $) について、$ s $ の $ i $ 文字目が `<` の場合は $ p_i\ <\ p_{i\ +\ 1} $ であり、$ s $ の $ i $ 文字目が `>` の場合は $ p_i\ >\ p_{i\ +\ 1} $ である。

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

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

4
<><

5

5
<<<<

1

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

217136290

### 制約 - $ N $ は整数である。 - $ 2\ \leq\ N\ \leq\ 3000 $ - $ s $ は長さ $ N\ -\ 1 $ の文字列である。 - $ s $ は `<` と `>` からなる。 ### Sample Explanation 1 条件を満たす順列は次の $ 5 $ 通りです。 - $ (1,\ 3,\ 2,\ 4) $ - $ (1,\ 4,\ 2,\ 3) $ - $ (2,\ 3,\ 1,\ 4) $ - $ (2,\ 4,\ 1,\ 3) $ - $ (3,\ 4,\ 1,\ 2) $ ### Sample Explanation 2 条件を満たす順列は次の $ 1 $ 通りです。 - $ (1,\ 2,\ 3,\ 4,\ 5) $ ### Sample Explanation 3 答えを $ 10^9\ +\ 7 $ で割った余りを出力することを忘れずに。