Problem Description

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 ().

Input Format

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 Format

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

6
))(()(

3

34
((((((((((((((((()))))))))))))))))

333606220

Hint

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