Правильная скобочная последовательность — это последовательность, состоящая из '(' и ')', которую можно превратить в корректное математическое выражение, вставив $$$1$$$ и $$$+$$$ любое количество раз в последовательность. Например, последовательность «()(()())» является правильной скобочной последовательностью, в то время как «())(()» или «(()» не являются.
Вам дана правильная скобочная последовательность $$$S$$$.
Рассмотрим сдвиг подпоследовательности$$$^{\text{∗}}$$$ вправо. Формально, когда подпоследовательность $$$S_{i_1} S_{i_2} \ldots S_{i_k}$$$ сдвигается вправо, буквы на выбранных индексах одновременно переназначаются следующим образом:
Другими словами, элемент на $$$j$$$-м выбранном индексе становится равен $$$((j-2) \bmod k + 1)$$$-й выбранной букве.
Например, когда $$$S$$$ равно «()(()())», сдвиг подпоследовательности $$$S_2 S_4$$$ изменяет $$$S$$$ на «((())())». С другой стороны, сдвиг $$$S_2 S_3 S_5$$$ изменяет $$$S$$$ на «())((())».
Пожалуйста, посчитайте, сколько непустых подпоследовательностей имеют свойство, что $$$S$$$ остаётся правильной при сдвиге подпоследовательности вправо. Поскольку ответ может быть очень большим, вам нужно вывести ответ по модулю $$$998\,244\,353$$$.
$$$^{\text{∗}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях. Две подпоследовательности считаются различными, если различаются множества позиций удаленных элементов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 300\,000$$$, $$$n$$$ четное).
Вторая строка каждого набора входных данных содержит правильную скобочную последовательность $$$S$$$ длиной $$$n$$$, представленную в виде строки без пробелов.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$300\,000$$$.
Для каждого набора входных данных выведите на отдельной строке ответ по модулю $$$998\,244\,353$$$.
42()4()()6(()())10()((())())
2828312
Для второго набора входных данных $$$8$$$ непустых подпоследовательностей, которые делают так, чтобы $$$S$$$ оставалась правильной при сдвиге вправо, следующие:
| Codeforces Round 1082 (Div. 1) |
|---|
| Закончено |
