P17460 [GESP202609 Level 7] Bracket Sequence

For strings $S$ and $T$, if deleting any number of characters from $S$ can produce $T$, then $T$ is a subsequence of $S$. In other words, $T$ is formed by selecting some characters from $S$ and concatenating them in index order. Two subsequences are different if and only if the sets of chosen indices are different. For example, `sun` is a subsequence of `sequence`, because deleting `eq`, `e`, and `ce` from `sequence` can produce `sun`. The string `sequence` has $2^8$ different subsequences, including the empty string. It also has three different subsequences `e`, because the $2$nd, $5$th, and $8$th characters of `sequence` are all `e`, and keeping each of these characters produces a different subsequence. For a string $S$, if $S$ satisfies the following conditions, then $S$ is a valid bracket sequence: - $S$ is the empty string, or - $S$ can be obtained by concatenating `(`, a valid bracket sequence, and `)`, or - $S$ can be obtained by concatenating two valid bracket sequences. For example, `()`, `()()`, `(())`, and `(()())` are all valid bracket sequences. But `(()` and `)(` are not valid bracket sequences. Given a string $S$ of length $n$ that contains only `(` and `)`, find how many of the $2^n$ subsequences of $S$ are valid bracket sequences. Since the answer may be very large, output the result modulo $10^9$. For example, when $S$ is `))(()(`, there are $3$ subsequences that are valid bracket sequences: the empty string and two different subsequences `()`.

The first line contains a positive integer $n$, indicating the length of the string $S$. The second line contains a string $S$ of length $n$ consisting only of `(` and `)`.

Output one line containing an integer, representing the number of valid bracket subsequences of $S$ modulo $10^9$.

For $40\%$ of the testdata, it is guaranteed that $1 \le n \le 400$. For all testdata, it is guaranteed that $1 \le n \le 2000$. Translated by ChatGPT 5