#AT20. Permutation

Permutation

[T] Permutation(dp_t)

来源: AtCoder Educational DP Contest - Problem T 原题时限:2 秒 / 内存:1024 MB

题目描述

设 NN 为正整数,给定一个长度为 N−1N-1 的、仅由 < 与 > 构成的字符串 ss。

求 (1,2,…,N)(1, 2, \ldots, N) 的排列 (p1,p2,…,pN)(p_1, p_2, \ldots, p_N) 中,满足以下条件的排列个数,对 109+710^9 + 7 取模:

  • 对于每个 ii(1≤i≤N−11 \le i \le N-1),若 ss 的第 ii 个字符为 <,则 pi<pi+1p_i < p_{i+1};若为 >,则 pi>pi+1p_i > p_{i+1}。

输入格式

输入由标准输入按以下格式给出:

N
s

输出格式

输出满足条件的排列数对 109+710^9 + 7 取模的结果。

数据范围

  • NN 为整数。
  • 2≤N≤30002 \le N \le 3000
  • ss 是长度为 N−1N-1 的字符串。
  • ss 由 < 与 > 组成。

样例 1

输入:

4
<><

输出:

5

样例 2

输入:

5
<<<<

输出:

1

样例 3

输入:

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

输出:

217136290