B2. Под-ПСП (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно вычислить сумму счётов всех подпоследовательностей $$$s$$$; $$$s$$$ не обязательно является правильной скобочной последовательностью, и ограничения на $$$n$$$ ниже.

Скажем, что скобочная последовательность $$$a$$$ лучше, чем скобочная последовательность $$$b$$$, если выполняется одно из следующих условий:

  • $$$b$$$ является префиксом $$$a$$$, но $$$a \ne b$$$; или
  • пусть $$$i$$$ — это первая позиция (если она существует), где $$$a_i \neq b_i$$$, тогда $$$\color{red}{a_i = \texttt{(}}$$$ и $$$\color{red}{b_i = \texttt{)}}$$$.

Для произвольной скобочной последовательности $$$t$$$ определим её счёт следующим образом:

  • Если $$$t$$$ не является правильной скобочной последовательностью$$$^{\text{∗}}$$$, счёт равен $$$0$$$.
  • Если существует правильная скобочная подпоследовательность $$$^{\text{†}}$$$ $$$r$$$ последовательности $$$t$$$, такая что $$$r$$$ является лучше, чем $$$t$$$, то счёт равен максимальному значению $$$|r|$$$ по всем таким подпоследовательностям $$$r$$$.
  • В противном случае счёт равен $$$0$$$.

Другими словами, счёт $$$t$$$ — это длина самой длинной правильной скобочной подпоследовательности $$$t$$$, которая лучше, чем $$$t$$$. Если $$$t$$$ не является правильной скобочной последовательностью, или если не существует правильной подпоследовательности, которая лучше, чем $$$t$$$, счёт равен $$$0$$$.

Вам дана скобочная последовательность $$$s$$$ длиной $$$n$$$. Найдите сумму счётов всех непустых подпоследовательностей $$$s$$$ по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Правильная скобочная последовательность — это последовательность скобок, которую можно преобразовать в корректное арифметическое выражение, вставив символы $$$\texttt{1}$$$ и $$$\texttt{+}$$$ между исходными символами последовательности. Например:

  • последовательности скобок $$$\texttt{()()}$$$ и $$$\texttt{(())}$$$ являются правильными (возможные выражения — это $$$\texttt{(1)+(1)}$$$ и $$$\texttt{((1+1)+1)}$$$);
  • последовательности скобок $$$\texttt{)(}$$$, $$$\texttt{(}$$$ и $$$\texttt{)}$$$ не являются правильными.

$$$^{\text{†}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 30$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — длина строки $$$s$$$.

Вторая строка каждого набора входных данных содержит последовательность $$$s$$$ длиной $$$n$$$, состоящую только из символов $$$\texttt{(}$$$ и $$$\texttt{)}$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$100$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — сумму счётов всех подпоследовательностей $$$s$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
1
(
6
()()()
6
(())()
8
(())()()
22
()()())()()(()()()((()
Выходные данные
0
4
0
22
563070
Примечание

В первом наборе входных данных единственной непустой подпоследовательностью является $$$g = \texttt{(}$$$. Она не является правильной скобочной последовательностью, поэтому её счёт равен $$$0$$$, и общая сумма также равна $$$0$$$.

Во втором наборе входных данных рассмотрим $$$g = s = \texttt{()()()}$$$. Это правильная скобочная последовательность. Мы можем выбрать $$$r = \texttt{(())}$$$, которая является подпоследовательностью $$$g$$$. Первый индекс, где $$$r$$$ и $$$g$$$ отличаются, это $$$i = 2$$$. Поскольку $$$r_2 = \texttt{(}$$$ и $$$g_2 = \texttt{)}$$$, $$$r$$$ лучше, чем $$$g$$$. Следовательно, счёт $$$g$$$ равен $$$|r| = 4$$$. Все остальные непустые подпоследовательности $$$s$$$ имеют счета, равные $$$0$$$.