Задача . D1. Красивая скобочная последовательность (простая версия)

Это простая версия этой задачи. Единственное отличие в ограничении на \(n\) — длине входной строки. В этой версии, \(1 \leq n \leq 2000\). Сложная версия этой задачи не предлагается в раунде для второго дивизиона.

Определим правильную скобочную последовательность и ее глубину следующим образом:

• Пустая строка это правильная скобочная последовательность глубины \(0\);
• Если «s» это правильная скобочная последовательность глубины \(d\) тогда «(s)» это правильная скобочная последовательность глубины \(d + 1\);
• Если «s» и «t» это две правильные скобочные последовательности тогда их конкатенация «st» это правильная скобочная последовательность с глубиной равной максимальной из глубин \(s\) и \(t\).

Для (не обязательно правильной) скобочной последовательности \(s\) мы определяем ее глубину как максимальную глубину любой правильной скобочной последовательности, которая может быть получена с помощью удаления некоторых символов из \(s\) (возможно нуля). Например, скобочная последовательность \(s = \)«())(())» имеет глубину \(2\), потому что при удалении третьего символа мы получим правильную скобочную последовательность «()(())» глубины \(2\).

Дана строка \(a\), состоящая из символов '(', ')' и '?'. Рассмотрим все (не обязательно правильные) скобочные последовательности, получающиеся заменой всех символов '?' в строке \(a\) на '(' или ')'. Посчитайте сумму глубин всех таких скобочных последовательностей. Так как это число может быть очень большим, найдите его по модулю \(998244353\).

Взломы в первом дивизионе по этой задачи могут быть сделаны, только если простая и сложная версия этой задачи сданы.