D. Monocarp and the Set
combinatorics; data structures; math
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\).
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 ?).
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\).
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\).