AT_dp_t Permutation

题目描述

给定一个正整数 $N$ 和一个由小于号 < 和大于号 > 组成的长度为 $N-1$ 的字符串 $s$。

你需要找到一个排列 $(p_1,\ p_2,\ p_3,\ ...,\ p_N)$，满足对于任意 $i\ (1 \leq i \leq N-1)$，如果 $s_i$ 为 < 则 $p_i < p_{i+1}$，如果 $s_i$ 为 > 则 $p_i > p_{i+1}$。求满足性质的排列 $p$ 的方案数对 ${10}^{9}+7$ 取模后的值。

输入格式

请按照以下格式输入：

$N$

$s$

输出格式

输出满足条件的方案个数对 ${10}^{9}+7$ 取模后的值。

输入输出样例 #1

输入 #1

4
<><

输出 #1

5

输入输出样例 #2

输入 #2

5
<<<<

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

217136290

说明/提示

数据范围与约定

• $N$ 是正整数
• $2 \leq N \leq 3000$
• $s$ 是一个长度为 $N-1$ 的字符串
• 字符串 $s$ 包含字符 < 和 >

样例解释 1

有 $5$ 个满足条件的排列，分别是：

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

样例解释 2

有 $1$ 个满足条件的排列 $(1,\ 2,\ 3,\ 4,\ 5)$。

样例解释 3

注意输出结果要对 ${10}^{9}+7$ 取模。