{"problem":{"name":"Reverse Brackets","description":{"content":"A string is defined to be a **valid parenthesis sequence** if and only if it satisfies one of the following conditions: *   It is an empty string. *   There exists a valid parenthesis sequence $A$ su","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc194_d"},"statements":[{"statement_type":"Markdown","content":"A string is defined to be a **valid parenthesis sequence** if and only if it satisfies one of the following conditions:\n\n*   It is an empty string.\n*   There exists a valid parenthesis sequence $A$ such that the string is obtained by concatenating `(`, $A$, and `)` in this order.\n*   There exist non-empty valid parenthesis sequences $A$ and $B$ such that the string is obtained by concatenating $A$ and $B$ in this order.\n\nYou are given a valid parenthesis sequence $S$ of length $N$. You can perform the following operation any number of times:\n\n*   Choose a contiguous substring of $S$ that is a valid parenthesis sequence, and reverse it.\n\nHere, reversing the substring of $S$ from the $l$\\-th character to the $r$\\-th character means the following:\n\n*   For every integer $i$ satisfying $l \\leq i \\leq r$, simultaneously replace $S_i$ with `)` if $S_{l+r-i}$ is `(`, and with `(` if $S_{l+r-i}$ is `)`.(Note that reversing here is different from the usual definition of reversing.)\n\nFind the number, modulo $998244353$, of distinct strings $S$ that you can have at the end of the process.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $|S| = N$\n*   $S$ is a valid parenthesis sequence.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc194_d","tags":[],"sample_group":[["6\n(())()","2\n\nFor example, you can transform $S$ into `()(())` by doing the following:\n\n*   Choose the substring from the 1st to the 6th character of $S$. This is a valid parenthesis sequence. $S$ becomes `()(())`.\n\nThe only other string that can be formed is `(())()`. Thus, the answer is $2$."],["2\n()","1"]],"created_at":"2026-03-03 11:01:14"}}