D. Монокарп и множество
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть $$$n$$$ чисел $$$1, 2, \dots, n$$$ и множество (изначально пустое). Он $$$n$$$ раз добавляет свои числа в это множество в некотором порядке. Во время каждого шага он добавляет новое число (которого ранее не было в множестве). Другими словами, последовательность добавленных чисел является перестановкой длины $$$n$$$.

Каждый раз, когда Монокарп добавляет элемент в множество, кроме первого раза, он записывает символ:

  • если элемент, который Монокарп пытается добавить, становится максимальным элементом в множестве, Монокарп записывает символ >;
  • если элемент, который Монокарп пытается добавить, становится минимальным элементом в множестве, Монокарп записывает символ <;
  • если ни одно из вышеперечисленного не выполняется, Монокарп записывает символ ?.

Дана строка $$$s$$$ из $$$n-1$$$ символов, которая представляет записанные символы Монокарпом (в порядке их записи). Вам нужно обработать $$$m$$$ запросов к строке. Каждый запрос имеет следующий формат:

  • $$$i$$$ $$$c$$$ — заменить $$$s_i$$$ символом $$$c$$$.

Перед всеми запросами и после каждого запроса вам нужно вычислить количество различных способов упорядочить числа $$$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
Примечание

В первом примере до обработки запросов есть три способа упорядочить числа:

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

После последнего запроса есть один способ упорядочить числа:

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