Bracket Pairing

Interview

Time limit7sMemory limit1024 MB

Summary

Given a bracket string of length up to 20 with some positions unknown, count how many ways to fill the unknowns so the whole sequence becomes a valid bracket sequence over four bracket types.

Level: Medium5 of 10
Topics: Dynamic programming, String, Recursion, Combinatorics
Solved: No attempts yet

Problem

There are four types of brackets: round (), square [], curly {}, and angle <>. A bracket sequence is defined to be valid as follows:

An empty sequence is valid.
If X is a valid bracket sequence, then pXq is a valid bracket sequence, where p is an open bracket, q is a close bracket, and p and q are of the same type.
If X and Y are valid bracket sequences, then the concatenation of X and Y, Z = XY, is a valid bracket sequence.

You have a bracket sequence in which some brackets are given, but the others are unknown and represented by question marks ('?'). You shall fill in each unknown bracket using the four types of brackets described above and obtain a valid bracket sequence. How many different valid bracket sequences can you obtain?

Input

The input has a single line giving a non-empty bracket sequence. The length of the sequence is even and no larger than 20. All sequence characters are either one of the four types of open or close brackets, or a question mark denoting an unknown bracket. There is at least one question mark in the sequence.

Output

Output the number of different valid bracket sequences you can obtain.

Examples3

Example 1
Input
```
(??)
```
Expected output
```
5
```
Example 2
Input
```
(<{}>??]
```
Expected output
```
1
```
Example 3
Input
```
(?]]
```
Expected output
```
0
```