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