给定一个不同值的列表,我们用第一个最小值、第二个最小值和第三个最小值表示三个最小值(按递增顺序)。
如果以下语句适用于所有 $$$(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]$$$。