背景

题目描述

你发现了一枚未被销蚀的战戟，稍加清洗后，你认出了铭刻在上面的扭动的字符串。

扭动的字符串是长为 $n-1$ 并且由 <，> 组成的字符串 $s$ 。

并非随机生成，这是因为有无形的「大手」存在。

「大手」是长为 $n$ 的排列 $a$ ，即 $[1,n]$ 的每个整数恰好出现一次的序列，并且当 $s_i$ 为 < 时有 $a_i<a_{i+1}$ ，当 $s_i$ 为 > 时有 $a_i>a_{i+1}$ 。

你需要求出有多少种满足条件的「大手」，答案对 $10^9+7$ 取模。

输入

第一行为一个正整数 $n\ (2\leq n\leq 3000)$ ，表示排列的长度。

接下来的一行为一个长为 $n-1$ 且仅由 <，> 组成的字符串 $s$。

输出

仅一行为一个整数，表示满足条件的排列方案数，答案对 $10^9+7$ 取模。

样例

5
<<<<

1

合法排列共 1 种：(1, 2, 3, 4, 5) 。

4
<><

5

合法排列共 5 种：

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

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

217136290

来源

2025 UESTC ICPC Training for Dynamic Programming and Search