← 返回题目列表

Codeforces · 1654/H

H. 三个最小值

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

给定一个不同值的列表,我们用第一个最小值、第二个最小值和第三个最小值表示三个最小值(按递增顺序)。

如果以下语句适用于所有 $$$(l,r)$$$ 且 $$$1\le l < l+2 \le r\le n$$$ 的对,则排列 $$$p_1, p_2, \dots, p_n$$$ 是好的。

- 如果 $$$\{p_l, p_r\}$$$ 是(不一定按此顺序)$$$p_l, p_{l+1}, \dots, 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$$$,

- $$$p_i < p_{i+1}$$$ 如果 $$$s_i =$$$ "<";
- $$$p_i > p_{i+1}$$$ 如果 $$$s_i =$$$ ">”。

输入

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

第二行包含长度为$$$m$$$的字符串$$$s$$$,由字符“<”和“">”组成。

输出

打印单个整数:满足语句中描述的约束的良好排列的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

5 3
>>>

输出 #1

5

输入 #2

5 1
<

输出 #2

56

输入 #3

6 5
<<><>

输出 #3

23

输入#4

10 5
><<><

输出#4

83154

输入 #5

1008 20
<><<>>><<<<<>>>>>>>>

输出 #5

284142857

注意

在第一个测试中,有 $$$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 > p_2$$$;
- 满足 $$$p_2 > p_3$$$;
- 满足 $$$p_3 > p_4$$$。

在第二个测试中,有 $$$60$$$ 排列使得 $$$p_1 < 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]$$$。