Explanation

Given the prefix, we first calculate the number of open and closing brackets in the rest of the sequence. If there's $c$ closing brackets and $n$ characters left, the number of possible endings is $\binom{n}{c}$, though not all of them have to be valid.

To get our true answer, we subtract the number of invalid bracket combinations by instead thinking of a bracket sequence as a path on a grid. You can read an in-depth explanation here.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <iostream>

using namespace std;

const int MAXN = 1e6;
const int MOD = 1e9 + 7;

 Code Snippet: Combinatorics Functions (from module) (Click to expand)

int main() {

Copy
MAXN = 10**6
MOD = 10**9 + 7

fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)

 Code Snippet: Combinatorics Functions (from the module) (Click to expand)

n = int(input())
s = input()