CF1886D.Monocarp and the Set

Monocarp has $n$ numbers $1, 2, \dots, n$ and a set (initially empty). He adds his numbers to this set $n$ times in some order. During each step, he adds a new number (which has not been present in the set before). In other words, the sequence of added numbers is a permutation of length $n$.

Every time Monocarp adds an element into the set except for the first time, he writes out a character:

• if the element Monocarp is trying to insert becomes the maximum element in the set, Monocarp writes out the character >;
• if the element Monocarp is trying to insert becomes the minimum element in the set, Monocarp writes out the character <;
• if none of the above, Monocarp writes out the character ?.

You are given a string $s$ of $n-1$ characters, which represents the characters written out by Monocarp (in the order he wrote them out). You have to process $m$ queries to the string. Each query has the following format:

• $i$ $c$ — replace $s_i$ with the character $c$.

Both before processing the queries and after each query, you have to calculate the number of different ways to order the integers $1, 2, 3, \dots, n$ such that, if Monocarp inserts the integers into the set in that order, he gets the string $s$. Since the answers might be large, print them modulo $998244353$.

Monocarp 有 $n$ 个数 $1, 2, \dots, n$ 和一个（初始为空的）集合。他以某种顺序将这些数依次加入该集合，共进行 $n$ 次。每次操作中，他加入一个此前未在集合中出现过的新数。换言之，所加入数字的序列是长度为 $n$ 的一个排列。

除第一次插入外，Monocarp 每次向集合中插入一个元素时，都会写下如下一个字符：

• 若该插入元素成为集合中的最大值，则写下字符 >；
• 若该插入元素成为集合中的最小值，则写下字符 <；
• 若以上两种情况均不满足，则写下字符 ?。

你将得到一个长度为 $n-1$ 的字符串 $s$，它表示 Monocarp 所写出的字符序列（按书写顺序）。你需要处理 $m$ 个对该字符串的查询，每个查询格式如下：

• $i$ $c$ — 将 $s_i$ 替换为字符 $c$。

在处理查询之前，以及每次查询之后，你都需要计算：有多少种不同的方式对整数 $1, 2, 3, \dots, n$ 进行排列，使得 Monocarp 按该排列顺序将整数插入集合时，恰好得到字符串 $s$？由于答案可能很大，请对 $998244353$ 取模后输出。

The first line contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$; $1 \le m \le 3 \cdot 10^5$).

The second line contains the string $s$, consisting of exactly $n-1$ characters <, > and/or ?.

Then $m$ lines follow. Each of them represents a query. Each line contains an integer $i$ and a character $c$ ($1 \le i \le n-1$; $c$ is either <, >, or ?).

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$；$1 \le m \le 3 \cdot 10^5$）。

第二行包含一个字符串 $s$，其长度恰好为 $n-1$，由字符 <、> 和/或 ? 组成。

接下来是 $m$ 行，每行表示一个查询。每行包含一个整数 $i$ 和一个字符 $c$（$1 \le i \le n-1$；$c$ 为 <、> 或 ? 中的一个）。

Both before processing the queries and after each query, print one integer — the number of ways to order the integers $1, 2, 3, \dots, n$ such that, if Monocarp inserts the integers into the set in that order, he gets the string $s$. Since the answers might be large, print them modulo $998244353$.

在处理查询之前以及每次查询之后，输出一个整数——即排列整数 $1, 2, 3, \dots, n$ 的方案数，使得若 Monocarp 按该顺序将这些整数插入集合中，则恰好得到字符串 $s$。由于答案可能很大，请对 $998244353$ 取模后输出。

In the first example, there are three possible orderings before all queries:

• $3, 1, 2, 5, 4, 6$;
• $4, 1, 2, 5, 3, 6$;
• $4, 1, 3, 5, 2, 6$.

After the last query, there is only one possible ordering:

• $3, 5, 4, 6, 2, 1$.

在第一个例子中，所有查询之前的可能排列有三种：

• $3, 1, 2, 5, 4, 6$；
• $4, 1, 2, 5, 3, 6$；
• $4, 1, 3, 5, 2, 6$。

在最后一次查询之后，仅剩一种可能的排列：

• $3, 5, 4, 6, 2, 1$。