CF1654H.Three Minimums

Given a list of distinct values, we denote with first minimum, second minimum, and third minimum the three smallest values (in increasing order).

A permutation $p_1, p_2, \dots, p_n$ is good if the following statement holds for all pairs $(l,r)$ with $1\le l \lt l+2 \le r\le n$.

• If ${p_l, p_r}$ are (not necessarily in this order) the first and second minimum of $p_l, p_{l+1}, \dots, p_r$ then the third minimum of $p_l, p_{l+1},\dots, p_r$ is either $p_{l+1}$ or $p_{r-1}$.

You are given an integer $n$ and a string $s$ of length $m$ consisting of characters "<" and ">".

Count the number of good permutations $p_1, p_2,\dots, p_n$ such that, for all $1\le i\le m$,

• $p_i \lt p_{i+1}$ if $s_i =$ "<";
• $p_i \gt p_{i+1}$ if $s_i =$ ">".

As the result can be very large, you should print it modulo $998\,244\,353$.

给定一个由互不相同元素构成的列表，我们用“第一小值”、“第二小值”和“第三小值”分别表示该列表中三个最小的值（按升序排列）。

排列 $p_1, p_2, \dots, p_n$ 称为好排列，当且仅当对所有满足 $1\le l < l+2 \le r\le n$ 的数对 $(l,r)$，如下命题成立：

• 若 $\{p_l, p_r\}$（顺序不限）恰好是子数组 $p_l, p_{l+1}, \dots, p_r$ 中的第一小值与第二小值，则该子数组的第三小值必为 $p_{l+1}$ 或 $p_{r-1}$。

现给定一个整数 $n$ 和一个长度为 $m$ 的字符串 $s$，其中每个字符为 “<” 或 “>”。

请计算满足如下条件的好排列 $p_1, p_2,\dots, p_n$ 的个数：

• 对每个 $1\le i\le m$，
  • 若 $s_i =$ “<”，则 $p_i < p_{i+1}$；
  • 若 $s_i =$ “>”，则 $p_i > p_{i+1}$。

由于答案可能非常大，请将结果对 $998\,244\,353$ 取模后输出。

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \leq m \leq \min(100, n-1)$).

The second line contains a string $s$ of length $m$, consisting of characters "<" and ">".

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \leq m \leq \min(100, n-1)$）。

第二行包含一个长度为 $m$ 的字符串 $s$，由字符 "<" 和 ">" 组成。

Print a single integer: the number of good permutations satisfying the constraints described in the statement, modulo $998\,244\,353$.

输出一个整数：满足题目描述中约束条件的“好”排列的数量，对 $998\,244\,353$ 取模。

In the first test, there are $5$ good permutations satisfying the constraints given by the string $s$: $[4, 3, 2, 1, 5]$, $[5, 3, 2, 1, 4]$, $[5, 4, 2, 1, 3]$, $[5, 4, 3, 1, 2]$, $[5, 4, 3, 2, 1]$. Each of them

• is good;
• satisfies $p_1 \gt p_2$;
• satisfies $p_2 \gt p_3$;
• satisfies $p_3 \gt p_4$.

In the second test, there are $60$ permutations such that $p_1 \lt p_2$. Only $56$ of them are good: the permutations $[1, 4, 3, 5, 2]$, $[1, 5, 3, 4, 2]$, $[2, 4, 3, 5, 1]$, $[2, 5, 3, 4, 1]$ are not good because the required condition doesn't hold for $(l, r)$ = $(1, 5)$. For example, for the permutation $[2, 4, 3, 5, 1]$,

• the first minimum and the second minimum are $p_5$ and $p_1$, respectively (so they are ${p_l, p_r}$ up to reordering);
• the third minimum is $p_3$ (neither $p_{l+1}$ nor $p_{r-1}$).

In the third test, there are $23$ good permutations satisfying the constraints given by the string $s$: $[1, 2, 4, 3, 6, 5]$, $[1, 2, 5, 3, 6, 4]$, $[1, 2, 6, 3, 5, 4]$, $[1, 3, 4, 2, 6, 5]$, $[1, 3, 5, 2, 6, 4]$, $[1, 3, 6, 2, 5, 4]$, $[1, 4, 5, 2, 6, 3]$, $[1, 4, 6, 2, 5, 3]$, $[1, 5, 6, 2, 4, 3]$, $[2, 3, 4, 1, 6, 5]$, $[2, 3, 5, 1, 6, 4]$, $[2, 3, 6, 1, 5, 4]$, $[2, 4, 5, 1, 6, 3]$, $[2, 4, 6, 1, 5, 3]$, $[2, 5, 6, 1, 4, 3]$, $[3, 4, 5, 1, 6, 2]$, $[3, 4, 5, 2, 6, 1]$, $[3, 4, 6, 1, 5, 2]$, $[3, 4, 6, 2, 5, 1]$, $[3, 5, 6, 1, 4, 2]$, $[3, 5, 6, 2, 4, 1]$, $[4, 5, 6, 1, 3, 2]$, $[4, 5, 6, 2, 3, 1]$.

在第一个测试用例中，有 $5$ 个满足字符串 $s$ 所给约束条件的“好”排列：$[4, 3, 2, 1, 5]$、$[5, 3, 2, 1, 4]$、$[5, 4, 2, 1, 3]$、$[5, 4, 3, 1, 2]$、$[5, 4, 3, 2, 1]$。它们均

• 是“好”的；
• 满足 $p_1 \gt p_2$；
• 满足 $p_2 \gt p_3$；
• 满足 $p_3 \gt p_4$。

在第二个测试用例中，共有 $60$ 个满足 $p_1 \lt p_2$ 的排列；其中仅有 $56$ 个是“好”的：排列 $[1, 4, 3, 5, 2]$、$[1, 5, 3, 4, 2]$、$[2, 4, 3, 5, 1]$、$[2, 5, 3, 4, 1]$ 不是“好”的，因为对 $(l, r) = (1, 5)$ 这一区间，所要求的条件不成立。例如，对于排列 $[2, 4, 3, 5, 1]$，

• 第一小值与第二小值分别为 $p_5$ 和 $p_1$（因此它们恰好是 $\{p_l, p_r\}$，顺序可交换）；
• 第三小值为 $p_3$（既不是 $p_{l+1}$，也不是 $p_{r-1}$）。

在第三个测试用例中，有 $23$ 个满足字符串 $s$ 所给约束条件的“好”排列：$[1, 2, 4, 3, 6, 5]$、$[1, 2, 5, 3, 6, 4]$、$[1, 2, 6, 3, 5, 4]$、$[1, 3, 4, 2, 6, 5]$、$[1, 3, 5, 2, 6, 4]$、$[1, 3, 6, 2, 5, 4]$、$[1, 4, 5, 2, 6, 3]$、$[1, 4, 6, 2, 5, 3]$、$[1, 5, 6, 2, 4, 3]$、$[2, 3, 4, 1, 6, 5]$、$[2, 3, 5, 1, 6, 4]$、$[2, 3, 6, 1, 5, 4]$、$[2, 4, 5, 1, 6, 3]$、$[2, 4, 6, 1, 5, 3]$、$[2, 5, 6, 1, 4, 3]$、$[3, 4, 5, 1, 6, 2]$、$[3, 4, 5, 2, 6, 1]$、$[3, 4, 6, 1, 5, 2]$、$[3, 4, 6, 2, 5, 1]$、$[3, 5, 6, 1, 4, 2]$、$[3, 5, 6, 2, 4, 1]$、$[4, 5, 6, 1, 3, 2]$、$[4, 5, 6, 2, 3, 1]$。