问题陈述

设 $N$ 是一个正整数。给你一个长度为 $N - 1$ 的字符串 $s$ ，它由 < 和 > 组成。

求以 $10^9 + 7$ 为模数，满足以下条件的 $(1, 2, \ldots, N)$ 的排列 $(p_1, p_2, \ldots, p_N)$ 的个数：

• 对于每个 $i$ ( $1 \leq i \leq N - 1$ )，如果 $s$ 中的 $i$ -th 字符是 <，则为 $p_i \lt p_{i + 1}$ ；如果 $s$ 中的 $i$ -th 字符是 >，则为 $p_i \gt p_{i + 1}$ 。

限制因素

• $N$ 是整数。
• $2 \leq N \leq 3000$
• $s$ 是长度为 $N - 1$ 的字符串。
• $s$ 由 < 和 > 组成。

输入

输入内容由标准输入法提供，格式如下：

• $N$
• $s$

输出

打印满足条件的排列数，模数为 $10^9 + 7$ 。

4
<><

5

满足条件的排列组合有五种，如下所示：

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

5
<<<<

1

有一种排列满足条件，如下所示：

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

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

217136290

请务必打印出 $10^9 + 7$ 的模数。

来源

https://atcoder.jp/contests/dp/tasks/dp_t