#P18362. One Different Inequality
One Different Inequality
One Different Inequality
题目描述
给定整数 ,以及一个长度为 、仅由 < 和 > 组成的字符串 。
设 是 的一个排列。如果对于所有 :
- 当 为
<时,有 ; - 当 为
>时,有 ,
则称 是一个 Good Permutation。
如果 满足以下两个条件,则称它是一个 Wonderful Permutation:
- 是 Good Permutation;
- 在所有 Good Permutation 中, 满足 的下标 的数量最多。
求 Wonderful Permutation 的个数,对 取模。
输入格式
第一行一个整数 。
第二行一个长度为 的字符串 。
输出格式
输出 Wonderful Permutation 的个数对 取模后的结果。
数据范围
- 。
- 长度为 ,仅含
<、>。 - 每个输入文件只有一组数据。
样例输入 1
5
<<>>
样例输出 1
2
样例输入 2
40
<<>><>><>>>><><<><><><<>><<<<>><><<<>><
样例输出 2
535474657
样例解释
样例 1 中, 和 都满足给定不等式,满足相邻绝对差为 的下标数分别为 、。
可以证明该数量最多为 ,恰有两个排列达到最大值: 和 ,所以答案是 。