给定一个整数 $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\quad S$

请输出一个整数，表示答案。

部分分

• 若能解决满足 $2 \leq N \leq 10000$ 的额外限制，则可以获得 $20$ 分。

样例解释 1

良好排列的例子有 $(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$ 的最大个数是 $3$，而优秀排列有 $(1,2,5,4,3)$ 和 $(3,4,5,2,1)$ 两种。

数据范围

• $N$ 是整数
• $2 \leq N \leq 2 \times 10^5$
• $S$ 是长度为 $N-1$、仅由 < 和 > 组成的字符串。

由 ChatGPT 5 翻译