MREPLBRC - Counting The Way of Bracket Replacement

English Vietnamese

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 bracket0sequence, 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

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

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

Output

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

Sample

Input:
6
()()()

Output:
1 
Input:
10
(?([?)]?}?

Output:
3
Input:
16
???[???????]????

Output:
92202

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


Added by:psetter
Date:2009-03-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COCI 1th 07

hide comments
2022-01-11 03:29:52
If you are getting wrong answer, it may be due to the unclarity of the problem statement.
If the answer for a specific test case is 12300050, you should print 00050, NOT 50. If, however, the answer for a specific test case is 123, you should print 123, NOT 00123.

Last edit: 2022-01-12 05:41:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.