题目背景

Cause getting made you want more

And hoping made you hurt more

Someone tell me

Something comforting

题目描述

Porter Robinson 花了五年的时间制作了 Something Comforting 这首歌，Mivik 花了五天时间造出了一道和括号序列相关的题。但 Mivik 并不开心，因为他发现他不会造数据了！

Mivik 需要随机生成一个 合法 的括号序列，于是 Mivik 想了一会，写出了下面的算法：

#include <algorithm>
#include <string>

std::string generate(int n) { // 生成一个长度为 n * 2 的括号序列
	const int len = n * 2;
	bool arr[len]; // 0 代表左括号，1 代表右括号
	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); // 随机打乱这个数组
	for (int i = 0, j, sum = 0; i < len; ) {
		sum += arr[i]? -1: 1;
		if (sum < 0) { // 出现了不合法的位置
			for (j = i + 1; j < len; ++j) {
				sum += arr[j]? -1: 1;
				if (sum == 0) break;
			}
			// 现在 i 是第一个不合法的位置，j 是 i 后面第一个合法的位置
			// ( ( ) ) ) ) ( ( ( ) ( )
			//         i     j
			for (int k = i; k <= j; ++k)
				arr[k] ^= 1; // 把这段区间全部反转
			i = j + 1;
		} else ++i;
	}
	std::string ret;
	for (int i = 0; i < len; ++i)
		ret += arr[i]? ')': '(';
	return ret;
}

P.S. 为了给其它语言用户带来做题体验，这里 提供了多种语言对该算法的描述。

Mivik 十分开心，因为这个算法总能生成合法的括号序列。但不一会儿他就发现这个算法生成的括号序列并不均匀，也就是说，当 $n$ 固定时，所有合法的括号序列出现的概率并不均等。例如，Mivik 发现当 $n=3$ 时，()()() 被生成的概率要远大于 ((()))。

现在 Mivik 给了你一个 $n$ 和一个长度为 $2n$ 的 合法 括号序列，假设 std::random_shuffle （对于其它语言来说，shuffle）能够均匀随机地打乱一个数组，他想问问你这个括号序列通过上文的算法被生成的概率是多少。由于 Mivik 不喜欢小数，你需要输出这个概率对 $998244353$ 取模的结果。如果你不知道如何将一个有理数对质数取模，可以参考 有理数取模。

输入格式

第一行一个整数 $n$，意义同题面。

接下来输入一个长度为 $2n$ 的合法括号序列，意义同题面。

输出格式

输出一行一个整数，代表这个概率对 $998244353$ 取模的结果。

1
()

1

3
()(())

598946612

提示

样例解释

样例一：$n$ 为 1 时，无论怎样都只可能会生成 () 这一种合法的括号序列，因此概率为 1。

数据范围

对于全部数据，有 $1\le n\le 5\cdot 10^5$，且输入的括号序列合法。

Subtask 1（20 pts）：保证 $1\le n\le 5$。

Subtask 2（30 pts）：保证 $1\le n\le 1000$。

Subtask 3（50 pts）：无特殊限制。