У Монокарпа есть $$$n$$$ чисел $$$1, 2, \dots, n$$$ и множество (изначально пустое). Он $$$n$$$ раз добавляет свои числа в это множество в некотором порядке. Во время каждого шага он добавляет новое число (которого ранее не было в множестве). Другими словами, последовательность добавленных чисел является перестановкой длины $$$n$$$.
Каждый раз, когда Монокарп добавляет элемент в множество, кроме первого раза, он записывает символ:
Дана строка $$$s$$$ из $$$n-1$$$ символов, которая представляет записанные символы Монокарпом (в порядке их записи). Вам нужно обработать $$$m$$$ запросов к строке. Каждый запрос имеет следующий формат:
Перед всеми запросами и после каждого запроса вам нужно вычислить количество различных способов упорядочить числа $$$1, 2, 3, \dots, n$$$ таким образом, что если Монокарп вставляет числа в множество в этом порядке, он получает строку $$$s$$$. Поскольку ответы могут быть большими, выведите их по модулю $$$998244353$$$.
Первая строка содержит два целых числа $$$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$$$ может быть <, >, или ?).
Перед всеми запросами и после каждого запроса выведите одно целое число — количество способов упорядочить числа $$$1, 2, 3, \dots, n$$$ таким образом, чтобы, если Монокарп вставляет числа в множество в этом порядке, он получает строку $$$s$$$. Поскольку ответы могут быть большими, выведите их по модулю $$$998244353$$$.
6 4 <?>?> 1 ? 4 < 5 < 1 >
3 0 0 0 1
2 2 > 1 ? 1 <
1 0 1
В первом примере до обработки запросов есть три способа упорядочить числа:
После последнего запроса есть один способ упорядочить числа:
