排列计数（二）(Permutation Counting II)

题目描述

给定一个长为 n 的字符串 s，s 由 <、> 和 ? 构成。s 应该看作是一部分排列的模板，匹配 s 的排列需要满足以下条件：

1. 排列由 0 到 n 的整数组成，每个数字只出现一次，记作 a₀,a₁,⋯,aₙ
2. 若 sᵢ 为 <，则要求 aᵢ < aᵢ₊₁
3. 若 sᵢ 为 >，则要求 aᵢ > aᵢ₊₁
4. 若 sᵢ 为 ?，则 aᵢ 和 aᵢ₊₁ 的大小关系任意

请计算，有多少种排列可以匹配 s？

由于答案可能很大，输出方案数模 10⁹+7 的余数。

输入格式

第一行：单个字符串，表示给定的模板，只有 <，> 和 ? 三种字符。

输出格式

输出共一行：单个整数，表示方案数模 10⁹+7 的余数。

数据范围

设 s 的长度为 n，则有

• 对于 30% 的数据：1 ≤ n ≤ 10
• 对于 60% 的数据：1 ≤ n ≤ 100
• 对于 100% 的数据：1 ≤ n ≤ 1000

样例输入 #1

<<

样例输出 #1

1

样例输入 #2

<? #### 样例输出 #2 3 #### 知识点与难度 本题涉及的知识点从属于 **GESP 7级**，难度等级：**⭐⭐⭐**。 --- ### 测试点分布 | Subtask | 分值 | 测试点编号 | 说明 | |:-------:|:----:|:----------:|:-----| | 0 | 10 | 1~2 | 样例 | | 1 | 20 | 3~8 | 小规模 n≤10 / 特殊: 全 | | 2 | 15 | 9~11 | Hack: n=1 / Hack: 全? / Hack: 交替 | | 3 | 30 | 12~20 | 中规模 n≈100~500 / 大规模 n≈1000 压力 | | 4 | 25 | 21~25 | 随机 n=1~1000 回归 |