A regular bracket-sequence is a string of characters consisting only of opening and closing brackets, and satisfying the following conditions:

- An empty string is a regular bracket-sequence.
- If
`A`

is a regular bracket-sequence, then`(A)`

,`[A]`

and`{A}`

are also regular bracket-sequences. - If
`A`

and`B`

are regular bracket-sequences, then`AB`

is also a regular bracket-sequence. For example, the sequences`[({})]`

,`[](){}`

and`[{}]()[{}]`

are regular, but the sequences`[({{([`

,`[]({)}`

and`[{}])([{}]`

are not.

Ivica has found a string which looks like it could be a regular bracket-sequence. Some of the characters have become smudged and illegible, and could have been any character.

Write a program that calculates how many ways the illegible characters in the string can be replaced by brackets so that the result is a regular bracket-sequence. This number can be very large, so output only its last 5 digits.

#### Input Specification

The first line contains an even integer , the length of the string.

The second line contains the string. Illegible characters are represented by the `?`

character.

#### Output Specification

Output the number of regular bracket-sequences the string could have read.

#### Sample Input 1

```
6
()()()
```

#### Sample Output 1

`1`

#### Sample Input 2

```
10
(?([?)]?}?
```

#### Sample Output 2

`3`

#### Explanation for Sample Output 2

In the second example, the three matching regular bracket-sequences are `({([()])})`

, `()([()]{})`

and `([([])]{})`

.

#### Sample Input 3

```
16
???[???????]????
```

#### Sample Output 3

`92202`

## Comments