排列与不等号 - 代码源竞赛平台

题目描述

蜗蜗想把整数 $1,2,\ldots,N$ 各使用一次，排列成一个长度为 $N$ 的序列 $p$。

蜗蜗还给出了一个长度为 $N-1$ 的字符串 $s$，其中每个字符都是 < 或 >。对于每个 $1\le i<N$，排列必须满足以下要求：

• 如果 $s$ 的第 $i$ 个字符为 <，则 $p_i<p_{i+1}$；
• 如果 $s$ 的第 $i$ 个字符为 >，则 $p_i>p_{i+1}$。

请你求出满足所有要求的排列数量，答案对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $N$，表示排列的长度。

第二行包含一个长度为 $N-1$ 的字符串 $s$，表示相邻两个数之间的大小关系。

输出格式

输出一行一个整数，表示满足所有要求的排列数量对 $10^9+7$ 取模的结果。

样例

3
<>

2

样例解释

排列需要满足 $p_1<p_2$ 且 $p_2>p_3$。

满足条件的排列有 $(1,3,2)$ 和 $(2,3,1)$，因此答案为 $2$。

数据范围

对于 100% 的数据，保证 $2\le N\le 3000$，字符串 $s$ 的长度为 $N-1$，且只包含字符 < 和 >。