Дана последовательность \(A\), в которой каждый элемент записан в формате + x или -, где \(x\) — целое число.
Для последовательности \(S\), в которой каждый элемент записан в формате + x или -, определим \(f(S)\) следующим образом:
- Проходим по \(S\) от первого элемента до последнего и поддерживаем мультимножество \(T\), изначально пустое.
- Если элемент последовательности имеет вид + x, добавим \(x\) в \(T\). Иначе удалим наименьший элемент из \(T\) (если \(T\) пусто, ничего делать не нужно).
- После прохода по \(S\) посчитаем сумму всех элементов в \(T\). \(f(S)\) полагается равным этой сумме.
Последовательность \(b\) является подпоследовательностью последовательности \(a\), если \(b\) может быть получена из \(a\) удалением нуля или больше элементов без изменения порядка оставшихся элементов. Для всех подпоследовательностей \(B\) последовательности \(A\) посчитайте сумму \(f(B)\) по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число, равное ответу на задачу по модулю \(998\,244\,353\).
Примечание
В первом примере все возможные пары \(B\) и \(f(B)\) выглядят так:
- \(B=\) {}, \(f(B)=0\).
- \(B=\) {-}, \(f(B)=0\).
- \(B=\) {+ 1, -}, \(f(B)=0\).
- \(B=\) {-, + 1, -}, \(f(B)=0\).
- \(B=\) {+ 2, -}, \(f(B)=0\).
- \(B=\) {-, + 2, -}, \(f(B)=0\).
- \(B=\) {-}, \(f(B)=0\).
- \(B=\) {-, -}, \(f(B)=0\).
- \(B=\) {+ 1, + 2}, \(f(B)=3\).
- \(B=\) {+ 1, + 2, -}, \(f(B)=2\).
- \(B=\) {-, + 1, + 2}, \(f(B)=3\).
- \(B=\) {-, + 1, + 2, -}, \(f(B)=2\).
- \(B=\) {-, + 1}, \(f(B)=1\).
- \(B=\) {+ 1}, \(f(B)=1\).
- \(B=\) {-, + 2}, \(f(B)=2\).
- \(B=\) {+ 2}, \(f(B)=2\).
Сумма этих значений равна \(16\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
-
+ 1
+ 2
-
|
16
|
|
2
|
15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-
|
750759115
|