问题描述

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

找到满足以下条件的排列$(p_1, p_2, \ldots, p_N)$ $(1, 2, \ldots, 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$取模。

示例输入1

4
<><

示例输出1

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, 2, 3, 4, 5)$

示例输入3

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

示例输出3

217136290

注意要对结果取模$10^9 + 7$。