{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5000$\n*   $|S| = N$\n*   $S$ is a valid parenthesis sequence."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"6\n(())()"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"2\n()"},{"iden":"sample output 2","content":"1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}