Bracket Sequences II

#include <iostream>
 
using namespace std;
 
const int MAXN = 1e6;
const int MOD = 1e9 + 7;
 
// BeginCodeSnip{Combinatorics Functions (from module)}
long long fac[MAXN + 1];
long long inv[MAXN + 1];
 
long long exp(long long x, long long n, long long m) {
	x %= m;
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}
 
void factorial(long long p) {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % p; }
}
 
void inverses(long long p) {
	inv[MAXN] = exp(fac[MAXN], p - 2, p);
	for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % p; }
}
 
long long choose(long long n, long long r, long long p) {
	return fac[n] * inv[r] % p * inv[n - r] % p;
}
// EndCodeSnip
 
int main() {
	int n;
	string s;
	cin >> n >> s;
 
	// Odd length strings have no solution
	if (n % 2) {
		cout << 0 << endl;
		return 0;
	}
 
	// Count the open/closed brackets
	int closed = 0, open = 0;
	for (int i = 0; i < s.size(); i++) {
		closed += (s[i] == ')');
		open += (s[i] == '(');
		// The string becomes invalid
		if (closed > open) {
			cout << 0 << endl;
			return 0;
		}
	}
 
	// Too many open brackets
	if (2 * open > n) {
		cout << 0 << endl;
		return 0;
	}
 
	// Get the size of the remaining string
	n -= s.size();
 
	// Precompute combinatorial values
	factorial(MOD);
	inverses(MOD);
 
	// Count the # of remaining open brackets in the suffix
	int remaining_closed = (n + open - closed) / 2;
 
	long long total_combs = choose(n, remaining_closed, MOD);
	long long bad_combs = choose(n, remaining_closed + 1, MOD);
	// Subtract from the total # of valid string the # of invalid strings
	cout << (total_combs - bad_combs + MOD) % MOD << endl;
}

MAXN = 10**6
MOD = 10**9 + 7
 
fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)
 
 
# BeginCodeSnip{Combinatorics Functions (from the module)}
def exp(x: int, n: int, m: int) -> int:
	x %= m
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * x % m
		x = x * x % m
		n //= 2
	return res
 
 
def factorial():
	fac[0] = 1
	for i in range(1, MAXN + 1):
		fac[i] = fac[i - 1] * i % MOD
 
 
def inverses():
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD)
	for i in range(MAXN, 0, -1):
		inv[i - 1] = inv[i] * i % MOD
 
 
def choose(n: int, r: int) -> int:
	if n < r:
		return 0
	return fac[n] * inv[r] % MOD * inv[n - r] % MOD
 
 
# EndCodeSnip
 
n = int(input())
s = input()
 
# Odd length strings have no solution
if n % 2 == 1:
	print(0)
	exit()
 
# Count the open/closed brackets
closed, open = 0, 0
for i in range(len(s)):
	closed += s[i] == ")"
	open += s[i] == "("
 
	# The string becomes invalid
	if closed > open:
		print(0)
		exit()
 
# Too many open brackets
if 2 * open > n:
	print(0)
	exit()
 
n -= len(s)
 
factorial()
inverses()
 
# Count the number of remaining open brackets in the suffix
remaining_closed = (n + open - closed) // 2
total_combs = choose(n, remaining_closed)
bad_combs = choose(n, remaining_closed + 1)
 
# Subtract from the total # of valid string the # of invalid strings
print((total_combs - bad_combs + MOD) % MOD)