分数: 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.