Monocarp and the Set
Contest: Educational Codeforces Round 156 (Rated for Div. 2)
Difficulty rating: 2100
Tags: 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$$$.

Input format:
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 ?).

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
6 4
<?>?>
1 ?
4 <
5 <
1 >

Example output:
3
0
0
0
1

Example input:
2 2
>
1 ?
1 <

Example output:
1
0
1

Editorial:
The key observation to this problem is that it's much easier to consider the process in reverse. Suppose Monocarp has a set of integers $$$1, 2, \dots, n$$$, and starts removing elements from it one by one. During the $$$i$$$-th deletion, if $$$s_{n-i}$$$ is <, he removes the minimum element; if $$$s_{n-i}$$$ is >, he removes the maximum element; and if $$$s_{n-i}$$$ is ?, he removes any element which is neither the minimum nor the maximum.
If you consider the process backwards, it's quite easy to see that it doesn't actually matter which numbers are present in the set; we are interested only in their quantity. So, for each action, we can choose an element to remove independently: if $$$s_{n-i}$$$ is < or >, there is only one way, otherwise, there are $$$k-2$$$ ways, where $$$k$$$ is the number of elements in the set (for the $$$i$$$-th deletion operation, it is $$$n-i+1$$$).
So, the answer to the problem is the product of $$$j-1$$$ for every character $$$s_j$$$ that is equal to ?.
To recalculate the answer efficiently when you change a character, you can use one of the following options:
• build a segment tree with operation "product on segment modulo $$$998244353$$$";
• or use modular inverse to maintain division operations. Note that sometimes you have to "divide by zero", i. e. remove the zero from the product (when $$$s_1$$$ changes from ? to another character); to handle it, you can store the product for every $$$s_i$$$ from $$$2$$$ to $$$n-1$$$, and explicitly multiply it by $$$0$$$ before printing when $$$s_1$$$ is ?.