Something Comforting
题目背景
> 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 想了一会，写出了下面的算法：
```cpp
#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. 为了给其它语言用户带来做题体验，[这里](https://www.luogu.com.cn/paste/wof8zjn8) 提供了多种语言对该算法的描述。
Mivik 十分开心，因为这个算法总能生成合法的括号序列。但不一会儿他就发现这个算法生成的括号序列并不均匀，也就是说，当 $n$ 固定时，所有合法的括号序列出现的概率并不均等。例如，Mivik 发现当 $n=3$ 时，`()()()` 被生成的概率要远大于 `((()))`。
现在 Mivik 给了你一个 $n$ 和一个长度为 $2n$ 的 **合法** 括号序列，假设 `std::random_shuffle` （对于其它语言来说，`shuffle`）能够均匀随机地打乱一个数组，他想问问你这个括号序列通过上文的算法被生成的概率是多少。由于 Mivik 不喜欢小数，你需要输出这个概率对 $998244353$ 取模的结果。如果你不知道如何将一个有理数对质数取模，可以参考 [有理数取模](https://www.luogu.com.cn/problem/P2613)。
输入输出格式
输入格式
第一行一个整数 $n$，意义同题面。
接下来输入一个长度为 $2n$ 的合法括号序列，意义同题面。
输出格式
输出一行一个整数，代表这个概率对 $998244353$ 取模的结果。
输入输出样例
输入样例 #1
1
()输出样例 #1
1输入样例 #2
3
()(())输出样例 #2
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）：无特殊限制。