Дана последовательность \(A\), в которой каждый элемент записан в формате + x или -, где \(x\) — целое число.
Для последовательности \(S\), в которой каждый элемент записан в формате + x или -, определим \(f(S)\) следующим образом:
Последовательность \(b\) является подпоследовательностью последовательности \(a\), если \(b\) может быть получена из \(a\) удалением нуля или больше элементов без изменения порядка оставшихся элементов. Для всех подпоследовательностей \(B\) последовательности \(A\) посчитайте сумму \(f(B)\) по модулю \(998\,244\,353\).
Первая строка содержит целое число \(n\) (\(1\leq n\leq 500\)) – длину \(A\).
Каждая из следующих \(n\) строк начинается с символа операции + или -. Если символ равен +, то за ним следует целое число \(x\) (\(1\le x<998\,244\,353\)). \(i\)-я строка из этих \(n\) строк описывает \(i\)-й элемент \(A\).
Выведите одно целое число, равное ответу на задачу по модулю \(998\,244\,353\).
В первом примере все возможные пары \(B\) и \(f(B)\) выглядят так:
Сумма этих значений равна \(16\).
4 - + 1 + 2 -
16
15 + 2432543 - + 4567886 + 65638788 - + 578943 - - + 62356680 - + 711111 - + 998244352 - -
750759115
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач