同学出的，但是现在同学不在，我只有一份没有注释的代码，想问问这道题怎么做的，最后的组合数式子是怎么推出来的。

规定合法的括号序列为：

• 空串是合法的括号序列。

• 若 $A$ 是合法的括号序列，则 $(A)$ 也是合法的括号序列。

• 若 $A$ 和 $B$ 均为合法的括号序列，则 $AB$ 也是合法的括号序列。

给定一个整数 $n$ 和一个初始有一些括号的双端队列。

你需要连续进行 $n$ 次操作：

• 每次操作在双端队列的队首或队尾添加一个左括号或右括号。

请求出有多少种不同的添加括号的方式，使得从双端队列队首依次取出的括号构成的括号序列合法。

记向队首添加的括号序列为 $A$，向队尾添加的括号序列为 $B$，则我们认为两种添加括号的方式不同，当且仅当有 $A$ 或 $B$ 中至少存在一个不同。

由于答案可能很大，所以你只需要求出答案对 $998244353$ 取模后的值。

多组测试数据。

第一行一个正整数 $T$ 表示数据组数，每组数据两行，第一行一个字符串 $S$ 表示括号序列，第二行一个正整数 $n$ 表示操作次数。

样例输入：

4
()
2
(()((()
7
(()))))))()
23
()
200000

样例输出：

3
28
1307504
926770616

$1 \leqslant n,\sum|S|\leqslant2\times10^{5}$。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,mod=998244353;
int T;
string s;
int m;
int p[N],inv[N];
int qpow(int x,int p){
	int res=1;
	while(p){
		if(p&1){
			res=res*x%mod;
		}
		x=x*x%mod;
		p>>=1;
	}
	return res;
}
int C(int n,int m){
	if(n<0||m<0||n<m){
		return 0;
	}
	return p[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
	p[0]=inv[0]=1;
	for(int i=1;i<=500000;i++){
		p[i]=p[i-1]*i%mod;
		inv[i]=qpow(p[i],mod-2);
	}
	cin>>T;
	while(T--){
		cin>>s>>m;
		int n=s.size();
		s=' '+s;
		int dis=0,minn=0;
		for(int i=1;i<=n;i++){
			dis=dis+(s[i]=='(')-(s[i]==')');
			minn=min(minn,dis);
		}
//		cout<<n<<' '<<m<<' '<<dis<<' '<<minn<<endl;
		if((m+n)&1){
			cout<<0<<endl;
			continue;
		}
		dis=-dis,minn=-minn;
		cout<<C(m+1,(m-dis)/2+minn+1)<<endl;
	}
    return 0;
}