Brackets

Time limit1sMemory limit128 MB

Summary

Count, modulo 1e9+9, the ways to turn some matching '(' '(' pairs back into '[' ']' so the bracket string becomes valid with at least one square pair.

Level: Medium6 of 10
Topics: Dynamic programming, Stack, String
Solved: No attempts yet

Problem

A valid bracket string is defined as follows.

() and [] are valid bracket strings.
If A is a valid bracket string, then (A) and [A] are also valid bracket strings.
If A and B are valid bracket strings, then their concatenation AB is also a valid bracket string.

Take any valid bracket string that contains at least one pair of square brackets (a [ and its matching ]), and replace every square bracket [ and ] with the character (. The resulting string is called a broken bracket string.

For example, (( and ((((())) are broken bracket strings. From (( you can recover the single valid bracket string []. From ((((())) you can recover the following four valid bracket strings: []((())), ([](())), (([]())), ((([]))).

Given a broken bracket string, write a program that counts how many valid bracket strings can be recovered from it.

Input

The first line contains the length N (2 ≤ N ≤ 30000) of the broken bracket string. The second line contains the broken bracket string of length N, consisting only of ( and ).

Output

Print, on the first line, the number of valid bracket strings that can be recovered from the given broken bracket string, modulo 1,000,000,009.

Examples4

Example 1
Input
```
4
((()
```
Expected output
```
2
```
Example 2
Input
```
8
((((((((
```
Expected output
```
14
```
Example 3
Input
```
2
((
```
Expected output
```
1
```
Example 4
Input
```
8
((((()))
```
Expected output
```
4
```