配点 : $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$) について、$s$ の $i$ 文字目が < の場合は $p_i < p_{i + 1}$ であり、$s$ の $i$ 文字目が > の場合は $p_i > p_{i + 1}$ である。

制約

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

入力

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

$N$

$s$

出力

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

4
<><

5

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

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

5
<<<<

1

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

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

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

217136290

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