Description

A valid bracket sequence is defined as follows:

• () and [] are valid bracket sequences.
• If $A$ is a valid bracket sequence, then $(A)$ and $[A]$ are also valid bracket sequences.
• If $A$ and $B$ are both valid bracket sequences, then $AB$ is also a valid bracket sequence.

For a valid bracket sequence that contains at least one pair of square brackets, we can replace both [ and ] with (, and then we may obtain an invalid bracket sequence.

For example, (( and ((((())) are both invalid bracket sequences. The former can be transformed from the valid bracket sequence \[]. The latter can be transformed from the following four valid bracket sequences: \[]((())), (\[](())), ((\[]())), and (((\[]))).

Now you are given an invalid bracket sequence. Find how many valid bracket sequences can become the given sequence after replacing the square brackets in them with (.

Input Format

The first line contains a positive integer $n$, which denotes the length of the given invalid bracket sequence.
The second line contains a string of length $n$, representing the given sequence, which contains only ( and ).

Output Format

Output the number of valid bracket sequences that meet the requirement modulo $10^9+9$.

4
((()

2

8
((((((((

14

Hint

Sample Explanation #1.

There are two valid bracket sequences that satisfy the condition: \[]() and ([]).

Constraints.

• For 20% of the testdata, $n \leq 50$.
• For 50% of the testdata, $n \leq 1000$.
• For 100% of the testdata, $2 \leq n \leq 30000$.

Notes.

Translated from BalticOI 2012 Day1 T1. Brackets.

Translated by ChatGPT 5