24582번 - Bracket Pairing 다국어

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

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 the number of different valid bracket sequences you can obtain.