CF1886D Monocarp and the Set

Monocarp 有 $n$ 个数字 $1, 2, \dots, n$ 和一个集合（初始为空）。他以某种顺序将这些数字依次加入集合中，每次加入一个新的、之前未出现过的数字。换句话说，加入数字的序列是 $1$ 到 $n$ 的一个排列。 每当 Monocarp 往集合中加入一个元素（除了第一次）时，他会写下一个字符： - 如果当前加入的元素成为集合中的最大值，Monocarp 写下字符 $>$； - 如果当前加入的元素成为集合中的最小值，Monocarp 写下字符 $

第一行包含两个整数 $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$ 为 $$ 或 $?$）。

在处理所有查询之前以及每次查询后，输出一个整数，表示有多少种排列方式，使得 Monocarp 按这种顺序插入数字后，得到的字符串正好是 $s$。每个答案对 $998244353$ 取模。

在第一个样例中，初始时有三种可能的排列： - $3, 1, 2, 5, 4, 6$； - $4, 1, 2, 5, 3, 6$； - $4, 1, 3, 5, 2, 6$。 在最后一个查询后，只剩下一种可能的排列： - $3, 5, 4, 6, 2, 1$。 由 ChatGPT 4.1 翻译