#P18362. One Different Inequality

One Different Inequality

One Different Inequality

题目描述

给定整数 NN,以及一个长度为 N−1N-1、仅由 < 和 > 组成的字符串 SS。

设 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N) 是 (1,2,…,N)(1,2,\ldots,N) 的一个排列。如果对于所有 1≤i≤N−11\le i\le N-1:

  • 当 SiS_i 为 < 时,有 Pi<Pi+1P_i<P_{i+1};
  • 当 SiS_i 为 > 时,有 Pi>Pi+1P_i>P_{i+1},

则称 PP 是一个 Good Permutation。

如果 PP 满足以下两个条件,则称它是一个 Wonderful Permutation:

  • PP 是 Good Permutation;
  • 在所有 Good Permutation 中,PP 满足 ∣Pi−Pi+1∣=1|P_i-P_{i+1}|=1 的下标 ii 的数量最多。

求 Wonderful Permutation 的个数,对 998244353998244353 取模。

输入格式

第一行一个整数 NN。

第二行一个长度为 N−1N-1 的字符串 SS。

输出格式

输出 Wonderful Permutation 的个数对 998244353998244353 取模后的结果。

数据范围

  • 2≤N≤2×1052\le N\le2\times10^5。
  • SS 长度为 N−1N-1,仅含 <、>。
  • 每个输入文件只有一组数据。

样例输入 1

5
<<>>

样例输出 1

2

样例输入 2

40
<<>><>><>>>><><<><><><<>><<<<>><><<<>><

样例输出 2

535474657

样例解释

样例 1 中,(1,2,5,4,3)(1,2,5,4,3) 和 (2,3,5,4,1)(2,3,5,4,1) 都满足给定不等式,满足相邻绝对差为 11 的下标数分别为 33、22。

可以证明该数量最多为 33,恰有两个排列达到最大值:(1,2,5,4,3)(1,2,5,4,3) 和 (3,4,5,2,1)(3,4,5,2,1),所以答案是 22。