Description

Porter Robinson spent five years making the song Something Comforting, and Mivik spent five days making a problem related to bracket sequences. But Mivik is not happy, because he found that he does not know how to generate testdata anymore.

Mivik needs to randomly generate a valid bracket sequence, so after thinking for a while, he wrote the following algorithm:

#include <algorithm>
#include <string>

std::string generate(int n) { // generate a bracket sequence of length n * 2
	const int len = n * 2;
	bool arr[len]; // 0 means left bracket, 1 means right bracket
	for (int i = 0; i < n; ++i) arr[i] = 0;
	for (int i = n; i < len; ++i) arr[i] = 1;
	std::random_shuffle(arr, arr + len); // randomly shuffle this array
	for (int i = 0, j, sum = 0; i < len; ) {
		sum += arr[i]? -1: 1;
		if (sum < 0) { // an invalid position appears
			for (j = i + 1; j < len; ++j) {
				sum += arr[j]? -1: 1;
				if (sum == 0) break;
			}
			// now i is the first invalid position, and j is the first valid position after i
			// ( ( ) ) ) ) ( ( ( ) ( )
			//         i     j
			for (int k = i; k <= j; ++k)
				arr[k] ^= 1; // flip everything in this interval
			i = j + 1;
		} else ++i;
	}
	std::string ret;
	for (int i = 0; i < len; ++i)
		ret += arr[i]? ')': '(';
	return ret;
}

P.S. To provide a better experience for users of other languages, here is a description of this algorithm in multiple languages.

Mivik is very happy, because this algorithm can always generate a valid bracket sequence. But soon he发现 that the bracket sequences generated by this algorithm are not uniform. That is, when $n$ is fixed, the probabilities of all valid bracket sequences are not equal. For example, Mivik found that when $n=3$, the probability of generating ()()() is much larger than that of generating ((())).

Now Mivik gives you an $n$ and a valid bracket sequence of length $2n$. Assume std::random_shuffle (for other languages, shuffle) can uniformly randomly shuffle an array. He wants to know the probability that this bracket sequence is generated by the algorithm above. Since Mivik does not like decimals, you need to output the result of this probability modulo $998244353$. If you do not know how to take a rational number modulo a prime, you can refer to Rational Numbers Modulo.

Input Format

The first line contains an integer $n$, with the same meaning as in the statement.

Next, input a valid bracket sequence of length $2n$, with the same meaning as in the statement.

Output Format

Output one line with one integer, representing this probability modulo $998244353$.

1
()

1

3
()(())

598946612

Hint

Sample Explanation

Sample 1: When $n$ is 1, no matter what, the only possible valid bracket sequence that can be generated is (), so the probability is 1.

Constraints

For all data, $1\le n\le 5\cdot 10^5$, and the input bracket sequence is valid.

Subtask 1 (20 pts): $1\le n\le 5$.

Subtask 2 (30 pts): $1\le n\le 1000$.

Subtask 3 (50 pts): No additional constraints.

Translated by ChatGPT 5