Description

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$ 取模的结果。如果你不知道如何将一个有理数对质数取模，可以参考 有理数取模。

Input Format

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

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

Output Format

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

1
()

1

3
()(())

598946612

Hint

样例解释

样例一：$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）：无特殊限制。