A balanced bracket expression is a string that consists only of bracket characters viz. ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, and satisfies the following conditions:

1. The empty string is a balanced bracket expression.
2. If A is a balanced bracket expression, then (A), [A] and {A} are also balanced bracket expressions.
3. If A and B are balanced bracket expressions, then AB is also a balanced bracket expression.

[({})], [](){} and [{}]()[{}] are examples of balanced bracket expressions.

You are given a string that consists only of bracket characters, and one other character, ‘?’. In how many ways can the occurrences of ‘?’ in the string be replaced by brackets so that the result is a balanced bracket expression?

This number can be very large, so output only its last 5 digits. If the number is more than 10^5, then you must print the last five characters of the number, even if they are 0. if it is less that 10^5, just print the number directly.

Input

The first line contains an even integer N (2 <= N <= 200), the length of the string.

The second line contains the string.

Output

Output the number of balanced bracket expressions that can be obtained by replacing the occurrences of ‘?’ by bracket characters.

Example

Input 1:
6
()()()

Output 1:
1

Input 2:
10
(?([?)]?}?

Output 2:
3