题目描述

$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$ で割った余りを出力せよ。

题目大意

有一个长为 $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$ 的方案数。

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$ で割った余りを出力することを忘れずに。