← 返回题目列表

AtCoder · dp_t

T. 排列

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

让 N 是正整数。 给你一个字符串 s 长度 N - 1,包括 < 和 >.

求排列数 (p_1, p_2, \ldots, p_N) of (1, 2, \ldots, N) 满足以下条件,模 10^9 + 7:

  • 对于每个 i (1 \leq i \leq N - 1), p_i < p_{i + 1} 如果 i- 第一个字符 s is <,和 p_i > p_{i + 1} 如果 i- 第一个字符 s is >.

约束

  • 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.