← 返回题目列表

AtCoder · utpc2024_o

O. 一种不同的不等式

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

配点 : 100 点

問題文

整数 N 和< 或 给出 > 组成 还给出了 N-1 字符串 S 。 如果输入

(1,2,\dots,N) 的排列 当 P=(P_1,P_2,\dots,P_N) 。

P 满足以下条件时, 求P 是 给出了良好的排列 据说。

  • 全部 i\ (1 \leq i \leq N-1) ,S 的 i 第一个字母是 < 如果 P_i < P_{i+1} 、> 如果 P_i > P_{i+1} 成立。 当

另外, 请注意,不得访问P 满足以下所有条件时,P 是 给出了精彩排列。

  • P 是一个很好的排列。
  • |P_i-P_{i+1}|=1 如果 i\ (1 \leq i \leq N-1) 的数量是良好排列中最多的。

大量排列 除以 998244353 求余数。

制約

  • N 是一个整数
  • 2 \leq N \leq 2 \times 10^5
  • S 是 给出了 < 或 给出 > 组成 还给出了 N-1 字符串

部分点

  • 附加限制 如果正确答案是满足 2 \leq N \leq 10000 的数据集 如果正确答案是满足 20 点。

入力

输入是按以下格式从标准输入给出的。

N
S

出力

答案 将除以 1 行输出。 由于字符串以


入力例 1

5
<<>>

出力例 1

2

一个好的排列的例子是 给出 (1,2,5,4,3) 呀 (2,3,5,4,1) 。|P_i-P_{i+1}|=1 如果 i 的数量是 3,2 件。

良好的排列 |P_i-P_{i+1}|=1 如果 i 的最大数量为 我们可以证明 3 并且好的排列是 (1,2,5,4,3) 和 在 (3,4,5,2,1) 的 2 会有一个。


入力例 2

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

出力例 2

535474657