1. Engineering
  2. Computer Science
  3. coding zapis a regular bracketsequence is a string of characters...

Question: coding zapis a regular bracketsequence is a string of characters...

Question details

[Coding] Zapis

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 (Python or Java or C++) 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 SNS 2000 , 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.

(Don't answer by hand-writing)

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution