题目背景

我们不妨认为关于 USTC 为什么是这样的做这样一个合理的解释：

• science and technology 后面直接接 university 会显得定语太长。
• 以中国为名的大学应当使用 of China 结尾。

对于前者，当你想到 HUST, HKUST 时，应当没有反例吧？

对于后者，当你想到 RUC, OUC 时，应当也没有反例吧？

什么？有反例？那真是失策了，给一个例子吧？

题目描述

初始给定一个长度为 $n$ 的序列 $1,2,...,n$。

其中有 $k$ 个元素不需要进行操作。定义一次操作（参数为 $x$）如下：

• 首先找到序列中值为 $x$ 的元素，不妨 $a_p=x$。（必须保证存在 $a_p=x$）
• 找到最大的 $l<p$ 满足 $a_l$ 是后续操作的参数（若不存在则 $l=0$）
• 找到最小的 $r>p$ 满足 $a_r$ 是后续操作的参数（若不存在则 $r=\text{len}(a)+1$）。$\text{len}(a)$ 为序列的长度。
• 删除 $a_p$ 并对 $l+1\sim p-1$ 和 $p+1\sim r-1$ 位置上的数进行整体交换。正式化地，操作后如下：

$$a_1,...,a_l,\ a_{p+1},...,a_{r-1},\ a_{l+1},...,a_{p-1},\ a_r,... $$

现在，克露丝卡尔酱不给你 $n-k$ 个元素了。他会考虑这样一个问题：

对于剩下长度为 $k$ 的序列 $b_i$ 中，给定任意两个相邻位置的元素的大小关系，问会有多少种操作序列能会使得最终的结果满足条件呢？

但很可惜，她忘记了一些相邻位置的元素的大小关系，所以她只会给定某一些两个相邻位置的元素的大小关系。你能帮帮她吗？

答案对 $998,244,353$ 取模。

输入格式

第一行两个正整数 $n$ ($1\le n\le 10^6$) 和 $k$ ($2\le k\le n$)。

第二行是长度为 $k-1$ 的字符串 $s$，字符集为 $\{<, >, ?\}$。

若 $s_i$ 为 <，表示 $b_i<b_{i+1}$；若 $s_i$ 为 >，表示 $b_i>b_{i+1}$；若 $s_i$ 为 ?，表示不确定 $b_i$ 与 $b_{i+1}$ 的大小关系。（字符串下标从 $1$ 开始）

输出格式

共一个整数表示合法的操作序列的数量。答案对 $998,244,353$ 取模。

样例 #1

样例输入 #1

7 5
><<>

样例输出 #1

2

样例 #2

样例输入 #2

7 5
????

样例输出 #2

42

提示

对于样例 $1$：操作序列有且仅有 $[2, 6]$ 和 $[6, 2]$。

对于样例 $2$：任意从 $7$ 个正整数中选取有序数对（两个数不相同）均可。